Prepare the following exercises for discussion in class on Monday 20th February 2012.
Exercise 3.1
Show that CSP generalizes SAT formulating the following SAT problem as a
CSP:
| (x ∨ y ∨ ¬ z) ∧ (¬ w ∨ ¬ z) ∧ (w ∨ ¬ y ∨ z) |
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 P1 and P2 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 Model the following problem and report the
model in written form.
Steel Mill Slab Design
Steel is produced by casting molten iron into slabs. A steel mill can produce a finite number, σ, of slab sizes. An order has two properties, a colour corresponding to the route required through the steel mill and a weight. Given d input orders, the problem is to assign the orders to slabs, the number and size of which are also to be determined, such that the total weight of steel produced is minimised. This assignment is subject to two further constraints:
The colour constraints arise because it is expensive to cut up slabs in order to send them to different parts of the mill.
The above description is a simplification of a real industrial problem. For example, the problem may also include inventory matching, where surplus stock can be used to fulfil some of the orders.