Information

Deadline No deadline
Submission limit No limitation

Sign in

[Part1] Consistency


Question 1: Consistency AllDifferent

We consider the \(\mathit{AllDifferent}(x_1,x_2,x_3,x_4)\) constraint with domains \(D(x_1)=\{1,3,4\}, D(x_2)=\{1,3\}, D(x_3)=\{1,3\}, D(x_4)=\{1,4,5\}\).

Select all the correct statements:

Question 2:

A binary constraint \(C(X,Y)\) is represented visually (feasible solutions inside the green shapes).

The domains \(D(X)\) and \(D(Y)\) are also represented as small green rectangles on the axes.

insertion

The image displays the domains AFTER they have been pruned by the constraint.

Select all the true statements given the current represented domains:

Question 3: General assertions

Select all the correct statements given a constraint \(C(X,Y,Z)\) with three finite-domain integer variables in its scope:

Question 4: Range consistency

C is range-consistent iff

\(\forall 1 \leq i \leq n, \forall v_i \in D(i):\quad \exists (v_1,\dots,v_{i-1},v_{i+1},\dots,v_n) \in\) \([\min(D_1),\max(D_1)] \times \cdots \times [\min(D_{i-1}),\max(D_{i-1})] \times [\min(D_{i+1}),\max(D_{i+1})] \times \cdots \times [\min(D_n),\max(D_n)]\) \(\text{ such that } C(v_1,\dots,v_i,\ldots,v_n)\)

Select all the correct statements:

Question 5: Binary Sum

Consider the constraint \(X+Y=0\) with \(D(X)=[100,110]\) and \(D(Y)=[-1000,120] \cap [-105, 1000]\). Assuming a consistent (does not remove any solution) filtering algorithm for the constraint that achieves bound consistency (after its filtering the constraint is bound consistent), what will be \(D(X)\)?

Write your answer in the format \(\{v_1,v_2,...,v_n\}\) with \(v_i < v_i+1\). For instance, write \(\{6,10,13\}\) but not \(\{13,6,10\}\).