Part 4: Sum and Element Constraints

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

Theoretical Questions

Element1D Constraint

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 = 0, z = 2
y = 3, z = 3

Implement a propagator Element1D.java by following the ideas (also in the slides) for Element2D, which however do not lead to domain consistency for both variables. Check that your propagator passes the tests Element1DTest.java.

Also implement a propagator Element1DDomainConsistent.java that achieves domain consistency for both variables. Check that your propagator passes the tests Element1DDCTest.java.

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 bounds 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 propagator 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.

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.