Example: Grocery

This example illustrates that elimination of symmetries can dramatically reduce the size of search trees.

Problem Specification

A kid goes into a grocery store and buys four items. The cashier charges $ 7.11, the kid pays and is about to leave when the cashier calls the kid back, and says

``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?

Viewpoint

The viewpoint of our model consits in four variables A, B, C, and D, which stand for the prices of the four items. In order that the variables can be constrained to finite domains of integers, we assume that the prices are given in cents. To say that the sum of the four prices is 711, we impose the constraint A + B + C + D = 711, and to say that the product of the four prices is 711, we impose the constraint

A * B * C * D = 711 * 100 * 100 * 100

The 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,

A$\le$B$\le$C$\le$D

With these ordering constraints the model has a unique solution.

Branching Strategy

For this problem it is advantageous to use a first-fail strategy that splits the domain of the selected variable and tries the upper part of the domain first. This strategy leads to a much smaller search tree than the standard first-fail strategy, which tries the least possible value of the selected variable first.

<<1599>>

The use of defined constraints

In Listing 4 you will recognize that a new function is used - constrain. It demands for further explanation. Listing 3 shows an example how defined constraints are realized. A new datatype - constraint - to modularize propagators is declared. Here, a constraint can be a sum, a product or a '<' - relation. The procedure post(space,SUMV(xs) `= `c,FD.BND) creates a propagator that propagates $\sum_{{i=1}}^{n}$x_i = c where the x_i are the elements of xs and c is an integer constant. The other procedure productRelI propagates $\pi_{{i=1}}^{n}$x_i = c. To realize this you need a temporary variable for every product of two variables because FD.mult only can propagate x * y = z. Both procedures use predefined propagators from the FD library.

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)

Script

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.

A subtle symmetry

There exists another symmetry whose elimination leads to a much smaller search tree. For this we observe that 711 has the prime factor 79 (711 = 9 * 79). Since the product of the prices of the items is 711, we can assume without loss of generality that 79 is a prime factor of the price A of the first item. We adapt our script by replacing the statement

constrain (space, LEQ(a, b))

with

post(space, FD(a) `= `79 `* FD(tmp), FD.DOM)

The new propagator for

a = 79 * tmp

reduces the search tree of Grocery to 205 nodes. The solution of the problem is now found after exploring 44 nodes.