Prepare the following exercises for discussion in class on Friday 27th February 2012.
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)⟩ |
Define a propagator for x+y=d and then for ax+by=d. Finally, generalize it to the linear equality ∑ai xi = d.
The element constraint models the following very common situation: we have to decide which among four goods to buy; for each good we have a different prices; how to propagate the price while the variable is not yet assigned a good?
Model in gecode the following basic problem that involves building a house. The masonry, roofing, painting, etc. must be scheduled in such a manner that minimizes the overall completion date of the houses. Some tasks must necessarily take place before others, and these requirements are expressed through precedence constraints. Moreover, there are three workers, and each task requires any one of the three workers. A worker can be assigned to at most one task at a time. Each task, once started, may not be interrupted.
| tasks = ["masonry","carpentry","plumbing","ceiling","roofing","painting","windows", "facade","garden","moving"]; duration = [35,15,40,15, 5,10, 5,10, 5, 5]; demand = [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]; # tuple (tasks before; tasks after) setOfPrecedences = set( (masonry, carpentry), (masonry, plumbing), (masonry, ceiling), (carpentry, roofing), (ceiling, painting), (roofing, windows), (roofing, facade), (plumbing, facade), (roofing, garden), (plumbing, garden), (windows, moving), (facade, moving), (garden, moving), (painting, moving)); |
In Chapter 22 of the Gecode manual, there is a Gecode implementation of the propagator for x < y. How would you implement a propagator for max(x,y) = z. (You should first read Chapter 22 of the manual. You do not need to effectively implement it but have clear how you would do it.)