<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD><TITLE>4.1 Example: Grocery</TITLE><LINK href="ozdoc.css" rel="stylesheet" type="text/css"></HEAD><BODY><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node20.html">- Up -</A></TD><TD><A href="node22.html#section.elimination.family">Next >></A></TD></TR></TABLE><DIV id="section.elimination.grocery"><H2><A name="section.elimination.grocery">4.1 Example: Grocery</A></H2><P>This example illustrates that elimination of symmetries can dramatically reduce the size of search trees. </P><DIV class="unnumbered"><H3><A name="label55">Problem Specification</A></H3><P>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? </P></DIV><DIV class="unnumbered"><H3><A name="label56">Model</A></H3><P>Our model has four variables <IMG alt="A" src="latex98.png">, <IMG alt="B" src="latex39.png">, <IMG alt="C" src="latex31.png">, and <IMG alt="D" src="latex1.png">, 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 <IMG alt="A+B+C+D = 711" src="latex106.png">, and to say that the product of the four prices is 711, we impose the constraint </P><BLOCKQUOTE><P><IMG alt="A\cdot B\cdot C\cdot D = 711\cdot100\cdot100\cdot100" src="latex107.png"></P></BLOCKQUOTE><P> 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, </P><BLOCKQUOTE><P><IMG alt="A\le B\le C\le D." src="latex108.png"></P></BLOCKQUOTE><P> With these ordering constraints the model has a unique solution. </P></DIV><DIV class="unnumbered"><H3><A name="label57">Distribution Strategy</A></H3><P>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. </P><P></P><DIV class="figure" id="proggrocery"><HR><P><A name="proggrocery"></A></P></DIV><DL class="anonymous"><DD class="code"><CODE><SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">Grocery</SPAN> Root}<BR> A<SPAN class="keyword">#</SPAN>B<SPAN class="keyword">#</SPAN>C<SPAN class="keyword">#</SPAN>D = Root<BR> S = 711<BR><SPAN class="keyword">in</SPAN> <BR> Root <SPAN class="keyword">:::</SPAN> 0<SPAN class="keyword">#</SPAN>S<BR> A<SPAN class="keyword">+</SPAN>B<SPAN class="keyword">+</SPAN>C<SPAN class="keyword">+</SPAN>D <SPAN class="keyword">=:</SPAN> S<BR> A<SPAN class="keyword">*</SPAN>B<SPAN class="keyword">*</SPAN>C<SPAN class="keyword">*</SPAN>D <SPAN class="keyword">=:</SPAN> S<SPAN class="keyword">*</SPAN>100<SPAN class="keyword">*</SPAN>100<SPAN class="keyword">*</SPAN>100<BR> %% <SPAN class="comment">eliminate symmetries<BR></SPAN> A <SPAN class="keyword">=<:</SPAN> B<BR> B <SPAN class="keyword">=<:</SPAN> C<BR> C <SPAN class="keyword">=<:</SPAN> D<BR> {FD<SPAN class="keyword">.</SPAN>distribute generic(value:splitMax) Root}<BR><SPAN class="keyword">end</SPAN></CODE></DD></DL><DIV class="figure"><P class="caption"><STRONG>Figure 4.1:</STRONG> A script for the Grocery Puzzle.</P><HR></DIV><P> </P></DIV><DIV class="unnumbered"><H3><A name="label58">Script</A></H3><P>The script in <A href="node21.html#proggrocery">Figure 4.1</A> spawns a search tree with 5039 nodes. It will explore 566 nodes before it finds the unique solution <CODE>120<SPAN class="keyword">#</SPAN>125<SPAN class="keyword">#</SPAN>150<SPAN class="keyword">#</SPAN>316</CODE>. Without the ordering constraints the script explores more than three 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. </P></DIV><DIV class="unnumbered"><H3><A name="label59">A Subtle Symmetry</A></H3><P>There exists another symmetry whose elimination leads to a much smaller search tree. For this we observe that 711 has the prime factor 79 (<IMG alt="711=9\cdot79" src="latex109.png">). 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 <CODE>A</CODE> of the first item. We adapt our script by replacing the statement <CODE>A<SPAN class="keyword">=<:</SPAN>B</CODE> with </P><BLOCKQUOTE class="code"><CODE>A <SPAN class="keyword">=:</SPAN> 79<SPAN class="keyword">*</SPAN>{FD<SPAN class="keyword">.</SPAN>decl}</CODE></BLOCKQUOTE><P> The procedure <CODE>{FD<SPAN class="keyword">.</SPAN>decl X}</CODE> constrains its argument to an integer in the finite domain <CODE>0<SPAN class="keyword">#</SPAN>sup</CODE>, where <CODE>sup</CODE> stands for a large implementation-dependent integer (<CODE>134217726</CODE> in Mozart on Linux or Sparcs). </P><P>The new propagator for <CODE>A<SPAN class="keyword">=:</SPAN>79<SPAN class="keyword">*</SPAN>X</CODE> reduces the search tree of <CODE>Grocery</CODE> to 357 nodes, one order of magnitude less than before. The solution of the problem is now found after exploring 44 nodes.</P></DIV></DIV><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node20.html">- Up -</A></TD><TD><A href="node22.html#section.elimination.family">Next >></A></TD></TR></TABLE><HR><ADDRESS><A href="http://www.ps.uni-sb.de/~schulte/">Christian Schulte</A> and <A href="http://www.ps.uni-sb.de/~smolka/">Gert Smolka</A><BR><SPAN class="version">Version 1.4.0 (20090610)</SPAN></ADDRESS></BODY></HTML>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
bd5c3d824c3db63ffd9226c15941e6ad
>
files
>
1194
