- Problem Specification
- Viewpoint
- Branching Strategy
- The use of defined constraints
- Script
- A subtle symmetry

``Hold on, I multiplied the four items instead of adding them; I'll try again; Hah, with adding them the price still comes to $ 7.11 .''

What were the prices of the four items?

A * B * C * D = 711 * 100 * 100 * 100The model admits many different equivalent solutions since the prices of the items can be interchanged. We can eliminate these symmetries by imposing an order on the prices of the items, for instance,

With these ordering constraints the model has a unique solution.ABCD

<<1599>>

fun product'(space, _, 0, _) = FD.range(space, (1, 1)) | product'(space, xs, 1, _) = Vector.sub(xs, 0) | product'(space, xs, n, conlevel) = Vector.foldl (fn (x, a) => let val tmp = FD.range(space, (0, maxValue)) in FD.mult(space, a, x, tmp, conlevel);tmp end) (product'(space, #[], 0, conlevel))xs fun productRelI(space, xs, rel, c, conlevel) = FD.relI(space, product'(space, xs, Vector.length xs, conlevel), rel, c) datatype constraint = SUM of FD.intvar vector * int | PRD of FD.intvar vector * int | LEQ of FD.intvar * FD.intvar fun constrain(space, SUM(xs, c)) = post(space,SUMV(xs) `= `c,FD.BND) | constrain(space, PRD(xs, c)) = productRelI(space, xs, FD.EQ, c, FD.BND) | constrain(space, LEQ( x, y)) = FD.rel(space, x, FD.LQ, y)

fun grocery space = let (* problem variables *) val a = FD.range(space, (0, maxValue)) val b = FD.range(space, (0, maxValue)) val c = FD.range(space, (0, maxValue)) val d = FD.range(space, (0, maxValue)) val tmp = FD.range(space,(0, maxValue)) (* interface *) val prices = #[a, b, c, d] in (* problem constraints *) constrain(space, SUM(prices,711)); constrain(space, PRD(prices,maxValue)); (* symmetry breaking *) constrain(space, LEQ(a, b)); constrain(space, LEQ(b, c)); constrain(space, LEQ(c, d)); (* branching *) FD.branch(space,prices,FD.B_SIZE_MIN,FD.B_SPLIT_MAX); {a, b, c, d} end

The script in Listing 4 spawns a huge search tree. It will explore 304 nodes before it finds the unique solution {120 125 150 316}. Without the ordering constraints the script explores more than 450 times as many nodes before finding a first solution. We learn that the elimination of symmetries may make it easier to find the first solution.

constrain (space, LEQ(a, b))with

post(space, FD(a) `= `79 `* FD(tmp), FD.DOM)The new propagator for

a = 79 * tmpreduces the search tree of Grocery to 205 nodes. The solution of the problem is now found after exploring 44 nodes.

Andreas Rossberg 2006-08-28