Prepare the following exercises for discussion in class on Friday 25th February 2011.
Exercise 5.1 Recall the definition of domain
consistency and relaxed domain consistency such as bound(Z),
bound(D) and range consistency. What is the consistency level of
the following CSPs?
| P = ⟨ x1 ∈ {1,3}, x2 ∈ {1,3}, x3 ∈ {1,3}, x4 ∈ {1,3} C≡ alldifferent(x1,x2,x3,x4)⟩ |
| P = ⟨ x1 ∈ {1,2,3}, x2 ∈ {2,3}, x3 ∈ {2,3}, x4 ∈ {1,2,3,4}, C≡ alldifferent(x1,x2,x3,x4)⟩ |
| P = ⟨ x1 ∈ {1,3}, x2 ∈ {2}, x3 ∈ {1,2,3}, C≡ alldifferent(x1,x2,x3)⟩ |
| P = ⟨ x1 ∈ {1,3}, x2 ∈ {2}, x3 ∈ {1,3}, C≡ alldifferent(x1,x2,x3) ⟩ |
| P = ⟨ x1 ∈ {1,3}, x2 ∈ {1,3}, x3 ∈ {1,3}, C≡ alldifferent(x1,x2,x3)⟩ |
Exercise 5.2 You have seen the basic propagation rules
for linear inequalities in the lectures. Implement an AC5 propagator for
ax+by≤ c with a,b,c ∈ ℤ∖ 0 in Comet. Use the
template leq.co available at:
http://www.imada.sdu.dk/~marco/DM826/Resources/. Try to run the
program and check that you get correct solutions. Is your implementation
leading to domain consistency or bound consistency?
Exercise 5.3 In Chapter 22 of the Gecode manual, there
is a Gecode implementation of the propagator for x < y. Implement a
propagator for max(x,y) = z. (You should first read Chapter 22 of the
manual.)
Exercise 5.4 We now want to generalize the propagator
of exercise 5.2 to a bound consistent propagator for ∑ai xi = b
and implement it in Gecode.
As you should have learned in the previous exercise views, as IntVarView, provide a read/write interface to a variable. They can also slightly change how the variable behaves. A scale view, e.g., has the same interface as an IntVarView. However, it makes a variable x look like a scaled version, ax, for some integer constant a. They are mentioned in section 22.1.3 and you may use them in your implementation.
Test your implementation using the send more money example.