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

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

Exercise 4.1 Indicate which of the following CSP is arc consistent:

• ⟨ x ∈ 1, y∈ 0,1, z ∈ 0,1; x ∧ y = z ⟩
• ⟨ x ∈ 0,1, y∈ 0,1, z ∈ 1; x ∧ y = z ⟩

Exercise 4.2 A form of weaker arc consistency is directed arc consistency, which enforces consistency only in one direction. Decide if the following CSP ⟨ x ∈ [2..10], y∈ [3..7], x<y⟩ is directed arc consistent in the case of linear ordering y ≺ x and in the case x ≺ y.

Exercise 4.3 What is the computational cost of enforcing arc consistency in the binary CSP ⟨ x ∈ 1..1000, y ∈ 1..1000, z ∈ 1..1000; x<y, y<z,z<x ⟩? Polynomial, pseudopolynomial or exponential?

Exercise 4.4 Show that every CSP has an equivalent normalized form. Does the normalized form preserve also arc consistency?

Exercise 4.5 Consider the following normalized CSP ⟨ x ∈ [0..4], y∈ [1..5], z ∈ [5..10]; x <y, y<z, x<z. Is it path consistent?

Exercise 4.6 Prove that 2-path consistency implies q-path consistency.