DM826 - Modeling and Solving Constrained Optimization Problems
Sheet 3, Spring 2011 [pdf format]

Prepare the following exercises for discussion in class on Friday 18th February 2011.

Exercise 3.1 Show that CSP generalizes SAT formulating the following SAT problem as a CSP:

Exercise 3.2 (Domain-based tightenings) Given two CSP P and P′, we write P′ ≼ P iff and any instantiation I on Y ⊆ X _P locally inconsistent in P is locally inconsistent in P′ as well.

Consider the following CSP: P=⟨ X={x,y}, DE≡{D(x)={1,2,3},D(y)={1,2,3}}, C⟩. Construct two domain tightenings P₁ and P₂ of P (a domain tightening is P′ such that X _P′=X _P, DE′ ⊆ DE, C _P′= C _P) for which the relation ≼ defined above is in fact a partial order. (Assume C admits any combination of values as valid.)

Exercise 3.3 (Propagation on paper) Consider an initial domain expression {x ∈ {0, 1, 2, 3}, y ∈ {0, 1, 2, 3}} and two constraints x < y and y < x. Apply the propagation algorithm Revise2001 from the lecture using pen and paper.

Exercise 3.4 In sections 15.1 and 15.2 of the Comet manual it is explained how to implement propagators in COMET.

• Find similarities and differences between the procedure AC5 there described and the procedures AC3, AC4, AC6 and Revise2001.
• How would you modify the example if the arity of the constraint were three or if the case to handle were the same treated when explaining AC3, AC4, AC6, Revise2001?