DM841 - Heuristics and Constraint Programming for Discrete Optimization
Exercise Sheet [pdf format]

Exercise 1

Let V = {{x, y, z} and D(x)={3,4,5}, D(y)={0,1,2,3}, D(z)={1,5}}. Define one or more propagators implementing the constraint x≤ y . Compute the propagator on the constraint store defined. Is the propagator strong idempotent? Is it weak idempotent?

Exercise 2

Define a propagator for x+y=d and then for ax+by=d. Finally, generalize it to the linear equality ∑a_i x_i = d.

• Is it necessary to perform several iterations of your propagator? Is it idempotent?
• What type of consistency it produces? (domain or bound consistency level?)
• Apply the propagator to the following example: x=3y+5z, D(x)={2..7},D(y)={0..2},D(z)={−1..2}. Compare the result with your answer to the previous point.

Exercise 3 Usefulness of Weak Idempotency

Assume V = {x, y} and D(x)=[0 .. 3], D(y)= [0 .. 5] Consider the constraint 3x = 2y and the propagator p₃₂

Apply the propagator three times and state whether the propagator is strong idempotent. If it is not is there a constraint store for which it is weak idempotent?

Exercise 4

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.)

Exercise 5

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 price; how to propagate the price while the variable is not yet assigned a good?

• Define a way to handle this situation without using the element constraint.
• Define a propagator for the element(a,x,y) constraint.
• Is it necessary to perform several iterations of your propagator? Is it idempotent?
• What type of consistency it produces? (domain or bound consistency level?)
• Run your propagator on the following example: a=[4,5,7,9], D(x)={1,2,3}, D(y)={2..8}.
• Can you devise a clever data structure that would speed up the propagation? Would it be worth storing the data structure for successive iterations?
• In gecode the element constraint is used also to implement a particular type of channeling, namely, z=x_y, where y and z are single variables and x is an array of variables. Write formally the propagators for x,y,z for the constraint element(z,x,y).