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?



Solution


A propagator pleq for x ≤ y can be defined as follows:

p≤ (D)(x) = {n ∈ D(x) | n ≤ maxD(y)}
p≤ (D)(y) = {n ∈ D(y) | n ≥ minD(x)}
p≤ (D)(z) = D(z)

The propagator computes:

p≤(D)(x) = {n ∈ D(x) | n ≤ 3}
p≤(D)(y) = {n ∈ D(y) | n ≥ 3}
p≤(D)(z) = D(z)
{ D(x) = {3}, D(y)={3}, D(z)= {1, 5}}

The propagator pleq is weakly idempotent because the current space cannot be tighten by another application of the propagator. It is not strongly idempotent because if the domain of a variable changes then it might propagate again.



Exercise 2

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



Solution


Domain consistency:

D(x) ← {n ∈ D(x) | ∃ ny ∈ D(y), nz ∈ D(z) : n=ny+nz}

It reaches fixpoint:

∀ nx ∈ D(x) ∃ ny ∈ D(y), nz ∈ D(z) : n=ny+nz
∀ ny ∈ D(y) ∃ nx ∈ D(x), nz ∈ D(z) : n=nx−nz
∀ nz ∈ D(z) ∃ nx ∈ D(x), ny ∈ D(y) : n=nx−ny

Bound consistency bound(Z):

D(x) ← {n ∈ D(x) | n ≤ maxD(y) + maxD(z) ∧ n ≥ minD(y)+minD(z)}
∀ nx ∈ {minD(x),maxD(x)}
∃ ny ∈ [minD(y) .. maxD(y)]
∃ nz ∈ [minD(z) .. maxD(z)]
nx=nz+ny

x+y=z

x∈ {1,2,4,8}y ∈ {1,2,4}z ∈ {1,2,3,4,6} 
x∈ {2,4,8}y ∈ {1,3,4}z ∈ {1,3,4}domain
x∈ {2,4,8}y ∈ {1,3,4}z ∈ {1,2,3,4}bound(Z)
D(x) ← {n ∈ D(x) | minD(z) − maxD(y) ≤ n ≤ maxD(z) − minD(y)}
D(y) ← {n ∈ D(y) | minD(z) − maxD(x) ≤ n ≤ maxD(z) − minD(x)}
D(z) ← {n ∈ D(z) | minD(x) + minD(y) ≤ n ≤ maxD(x) + maxD(y)}

This is not idempotent



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 p32

p32 (D)(x) = D(x) ⋂ {⌈(2 minD(y))/3⌉ ,…, ⌊(2 maxD(y))/3⌋}
p32 (D)(y) = D(y) ⋂ {⌈(3 minD(x))/2⌉ , … , ⌊(3 maxD(x))/2⌋}

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?



Solution


The propagator p32 is not idempotent. Consider Then D′ = p32 (D) is

D′ (x) = [0 .. 3] ⋂ [0 .. ⌊ 10/3⌋] = [0 .. 3]
D′ (y) = [0 .. 5] ⋂ [0 .. ⌊ 9/2 ⌋] = [0 .. 4]

Now D″ = p32 (D′) is

D″(x) = [0 .. 3] ⋂ [0 .. ⌊ 8/3⌋] = [0 .. 2]
D″(y) = [0 .. 4] ⋂ [0 .. ⌊ 9/2⌋] = [0 .. 4]

Hence p32 (p32 (s)) = s″ ≠ s′ = p32 (D) and the propagator is not strong idempotent. Further D‴ = p32 (D″) is

D‴(x) = [0 .. 2] ⋂ [0 .. ⌊ 8/3⌋] = [0 .. 2]
D‴(y) = [0 .. 4] ⋂ [0 .. ⌊ 6/2⌋] = [0 .. 3]

The new bound for y is 3 and is obtained without rounding. In this case we are guaranteed that the proagator is at a fixedpoint. Knwoing that it is idempotent on D‴ is useful since we can avoid runnig the propagator.



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?