0. Assignment Instructions

Before starting with the Java implementation, read the assignment instructions and grading rules on the course web page: https://user.it.uu.se/~pierref/courses/COCP/assignments/assignment4/assignment4.pdf .

This part of the assignment is on the programming tasks of Modules 1 and 2 of the MiniCP on-line teaching materials.

For the first part of the programming tasks of this assignment, you will model a Graph Coloring Problem by using TinyCSP.

1. Graph Colouring

Go to the GraphColoringTinyCSP.java file within the tinycsp.examples package.

It contains one task inside the solve method, highlighted with a TODO. You will need to:

1. Create the variables for solving the problem (using TinyCSP.makeVariable()). Each variable should represent the color of a node.
2. Add constraints on the variables saying that two nodes connected by an edge (GraphColoringInstance.edges) cannot have the same color.
3. Return the first valid solution that you encounter.

public static int[] solve(GraphColoringInstance instance) {
    // TODO: solve the graph coloring problem using TinyCSP and return a solution
    // Hint: you can stop the search on first solution, throwing and catching an exception
    //       in the onSolution closure, or you can modify the dfs search
}

You can have a look at the NQueensTinyCSP.java class for inspiration on how to create the variables, add constraints, and process the solution.

Make the implementation in your personal repository that you have set up before (and pushe the changes to the main branch on github).

You can check that your implementation is correct by running the tests within GraphColoringTinyCSPTest.

For the second part of the programming tasks of this assignment, you will enhance your solver by implementing:

1. A new constructor to make creating variables easier;
2. A domain iterator over your variables; and
3. Your first constraint: the Maximum constraint.

2. Domain with an Arbitrary Set of Values

To use more easily the integer variables from MiniCP, you will implement a missing constructor within IntVarImpl.

public IntVarImpl(Solver cp, Set<Integer> values) {
    throw new NotImplementedException();
}

This exercise is straightforward: just create a dense domain and then remove the values not present in the set.

Check that your implementation passes the tests arbitrarySetDomainsMaxInt and arbitrarySetDomains from IntVarTest.java.

3. Implement a Domain Iterator

Many filtering algorithms require iteration over the values of a domain.

A naive (but correct) way of iterating over a domain is:

for (int v = x.min(); v <= x.max(); v++) {
    if (x.contains(v)) {
        // do something
    }
}

This method is rather inefficient because it will also consider the values that are not present in the domain. Instead, the fillArray method from StateSparseSet.java allows filling an array with all the values present in the sparse set. In case of an offset value of 0, you could even use the very efficient System.arraycopy.

The main advantage over the iterator mechanism is that no object is created (and thus garbage collected). Indeed dest is typically a container array stored as an instance variable and reused many times. It is important for efficiency to avoid creating objects on the heap at each execution of a propagator. Never forget that a propagate() method of Constraint may be called thousands of times per second.

This implementation using fillArray avoids the ConcurrentModificationException discussion when implementing an Iterator: should we allow modifying a domain while iterating on it? The answer here is very clear: you get a snapshot of the domain at the time of the call to fillArray and you can thus safely iterate over this dest array and modify the domain at the same time.

To do:

• Improve the efficiency of fillArray from StateSparseSet.java in order to use System.arraycopy when possible.
• Implement public int fillArray(int [] dest) in IntVarImpl.java.
• Check that your implementation passes all the tests from IntVarTest.java and StateSparseSetTest.java.

3. The Maximum Constraint

The maximum constraint links an array of variables x with one variable y such that y = maximum(x[0],x[1],...,x[n]).

Implement Maximum.java. Your algorithm needs to be bound-consistent:

1. Update the minimum and maximum of each x[i] based on the bounds of y
2. Update the minimum and maximum of y based on the bounds of all x[i]

The propagation itself should be done within the propagate() method. Within the post() method, you should register the constraints for the variables (through IntVar.propagateOnBoundChange()) and trigger a first time the propagation. You can have a look at the LessOrEqual.java constraint if you are unsure about the differences between a post() and a propagate() and need a working example to see how to start.

@Override
public void post() {
    // TODO very first filtering and register the propagation for changes:
    //  - call the constraint on all bound changes for the variables (x.propagateOnBoundChange(this))
    //  - call a first time the propagate() method to trigger the propagation
}

@Override
public void propagate() {
    // TODO the filtering itself:
    //  - update the min and max values of each x[i] based on the bounds of y
    //  - update the min and max values of y based on the bounds of all x[i]
}

Check that your implementation passes the tests MaximumTest.java.

Before submitting, remember to fetch the latest changes from upstream (the MiniCP GitHub repository).

Note that the original tests of the MiniCP GitHub repository will be run.