[Part5 Theory] AllDifferent Constraint

Question 1: AllDifferent: Bound Consistency

Consider the following domains:

D(X1) = {0,2}, D(X2) = {0,2}, D(X3) = {2,3,4,5}

What is the domain of X3 after bound-consistent filtering of the constraint AllDifferent(X1,X2,X3)?

D(X3) = {2,3,4,5}

An inconsistency is detected.

D(X3) = {3,4,5}

Question 2: AllDifferent: Forward-Checking Consistency

Select all the true statements:

A deactivated constraint will not be propagated, but since it is in the stacks of the constraints on the variables, the constraint will nevertheless be scanned.

Deactivating a constraint is not a reversible operation: the constraint will never be called again for the remainder of the search tree, even after backtracking.

The forward-checking filtering algorithm removes all the infeasible values: it achieves domain consistency.

The forward-checking filtering algorithm without the sparse-set trick (thus scanning all the variables every time in order to possibly remove a value) is faster than the binary decomposition.

Whatever the (deterministic) heuristic used for the variable and value selection for the n-Queens problem, the search tree explored with forward-checking filtering for AllDifferent is the same as with the binary decomposition (same number of nodes).

The forward-checking filtering algorithm for AllDifferent removes the same values as the binary decomposition.

Question 3: AllDifferent: Domain Consistency

Consider the following domains:

D(X1) = {0,2}, D(X2) = {0,2}, D(X3) = {2,3,4,5}

What is the domain of X3 after domain-consistent filtering of the constraint AllDifferent(X1,X2,X3)?

An inconsistency is detected.

D(X3) = {3,4,5}

D(X3) = {2,3,4,5}

Question 4: AllDifferent: Data Structures for Régin's Domain-Consistent Filtering Algorithm

Consider the following domains:

D(X1) = {0,2}, D(X2) = {0,2}, D(X3) = {1,2,3,4}

and the constraint AllDifferent(X1,X2,X3). Select all the true statements for domain-consistent filtering:

The node label of value 2 in the residual graph is 5.

The node indices 2 and 4 are in two different strongly connected components.

The number of strongly connected components in the residual graph is 3.

The node label of value 2 in the residual graph is 2.

The node label of value 2 in the residual graph is 6.

The node indices 2 and 4 are in the same strongly connected component.

The number of strongly connected components in the residual graph is 2.

Question 5: AllDifferent: Régin's Domain-Consistent Filtering Algorithm

Select all the true statements:

An edge belongs to some maximum matching (in the variable-value graph) if and only if for every maximum matching, it belongs to an even alternating cycle.

An edge belongs to some maximum matching (in the variable-value graph) if and only if for every maximum matching, it belongs to an alternating path.

The maximum matching needs to be stored in a stateful data-structure since it may not be valid anymore on backtrack.

Given a maximum matching (in the variable-value graph), the domain-consistent filtering algorithm for \(AllDifferent(X_1,\dots,X_n)\) can be implemented to run in \(O(|D(X_1)|+\dots+|D(X_n)|)\) time.

Deadline	No deadline
Submission limit	2 submissions every 1 hour(s)

Information

Sign in

Question 1: AllDifferent: Bound Consistency

Question 2: AllDifferent: Forward-Checking Consistency

Question 3: AllDifferent: Domain Consistency

Question 4: AllDifferent: Data Structures for Régin's Domain-Consistent Filtering Algorithm

Question 5: AllDifferent: Régin's Domain-Consistent Filtering Algorithm

Information

Sign in