1. Element1D Constraint - Bound-Consistent Propagator

Given an array T of integers and the variables y and z, the Element1D constraint enforces that z takes the value at index y of T: the relation T[y]=z must hold, where indexing starts from 0.

Assuming T=[1,3,5,7,3], the constraint holds for

y = 1, z = 3
y = 3, z = 7

but is violated for

y = 1, z = 1
y = 3, z = 5

Implement a propagator Element1D.java by following the ideas (also in the slides) for Element2D, which lead to bound consistency on z and domain consistency on y. Check that your implementation passes the tests Element1DTest.java.

2. Element1D Constraint - Domain-Consistent Propagator

Now that you have implemented a bound-consistent propagator for the Element1D constraint, you can implement another one for the same constraint, reaching domain consistency.

Within Element1DDomainConsistent.java, implement a propagator that achieves domain consistency for both variables.

One way to implement the domain-consistent version is to check if the constraint holds for every value within the domain of y and z. To iterate over their domains, you can use your efficient IntVar.fillArray that you implemented previously:

int size = y.fillArray(values);
for (int i = 0 ; i < size ; i++) {
    int valueOfY = values[i];
    // check if valueOfY (one element from the domain of y) is valid. Remove it otherwise
}

Keep in mind that values should be a container array stored as an instance variable from Element1DDomainConsistent 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.

Check that your implementation passes the tests Element1DDCTest.java.

3. Element1DVar Constraint with an Array of Variables

Implement a propagator Element1DVar.java. This constraint is more general than Element1D above, since T is here an array of variables.

The filtering algorithm is nontrivial, at least if you want to do it efficiently. Two directions of implementation are:

• The hybrid domain-bound consistent propagator achieves bound consistency for z and all the T[i] but domain consistency for y.
• The domain-consistent propagator achieves domain consistency for y, z, and all the T[i].

Check that your implementation passes the tests Element1DVarTest.java. Those tests do not check that your propagator achieves domain consistency for all the variables, so you have to write additional tests in order to help convince yourself that it does so, if you take that direction.

4. The Stable Matching Problem

Complete the partial model StableMatching.java. It makes use of the Element1DVar constraint you have just implemented and is also a good example of the manipulation of logical and reified constraints. Ensure that your implementation discovers all 6 solutions to the provided instance. Check that your implementation passes the tests StableMatchingTest.java.

Hint1: Some constraints will need to be modeled using Element1DVar when one of the arguments is a constant instead of a variable. To transform an int z into a variable, you can create an IntVar with z as its unique domain value, by using makeIntVar(cp, z, z):

IntVar[] T = ...;
IntVar y = ...;
int z = ...; // not an IntVar
// does not work
cp.post(new Element1DVar(T, y, z));
// this works!
cp.post(new Element1DVar(T, y, makeIntVar(cp, z, z)));

Hint2: Some constraints are modeled using implication. A static method implies is provided within StableMatching.java.