Part 2: Domains, Variables, Constraints

We ask you not to publish your solutions on a public repository. The instructors interested to get the source-code of the solutions can contact us.

Theoretical questions

Domain with an arbitrary set of values

Implement the missing constructor in IntVarImpl.java

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

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

Check that your implementation passes the tests IntVarTest.java

Implement a domain iterator

Many filtering algorithms require to iterate over the values of a domain.

A naive (but correct) way of iterating over the domains is:

for (int v = x.min(); v <= x.max(); x++) {
            if (x.contains(i)) {
                // 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 to fill 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 not object is created (and thus garbage collected). Indeed dest is typically a container array stored as an instance variable and reused many times. This 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 to modify 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 modifying the domain at the same time.

To do:

  • Improve the efficiency of fillArray from StateSparseSet.java to use ‘System.arraycopy’ when possible.
  • Implement public int fillArray(int [] dest) in IntVarImpl.java.
  • Check that your implementation passes the tests IntVarTest.java add also add more tests.

The absolute value constraint

Implement Absolute.java

Again you will realize that several directions of implementation are possible

  1. The full domain consistent version (use the fillArray method to iterate over domains)
  2. An hybrid domain-bound consistent one

Check that your implementation passes the tests AbsoluteTest.java

The maximum constraint

Implement Maximum.java

Implement a bound-consistent filtering algorithm

Check that your implementation passes the tests MaximumTest.java