In this assignment, you will enhance your solver by implementing
- A new constructor to create more easily your variables;
- A domain iterator over your variables;
- Your first constraint: the
Maximum
constraint.
1. 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.
2. 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(); 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 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 useSystem.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:
- Update the minimum and maximum of each
x[i]
based on the bounds ofy
- Update the minimum and maximum
y
based on the bounds of allx[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 each y based on the bounds of all x[i] }
Check that your implementation passes the tests MaximumTest.java.