/usr/share/mozart/doc/fdt/node39.html is in mozart-doc 1.4.0-8ubuntu1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 | <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD><TITLE>8.4 Example: Bin Packing</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="node38.html#section.reified.srat"><< Prev</A></TD><TD><A href="node35.html">- Up -</A></TD></TR></TABLE><DIV id="section.reified.bin"><H2><A name="section.reified.bin">8.4 Example: Bin Packing</A></H2><P>This example features a nontrivial model involving reified constraints, a three-dimensional distribution strategy optimizing a cost function, and nontrivial defined constraints. The script will employ explicit thread creations to prevent blocking. To optimize performance, the script will implement certain implicative constraints with conditionals rather than reified constraints. </P><DIV class="unnumbered"><H3><A name="label111">Problem Specification</A></H3><P>Given a supply of components and bins of different types, compile a packing lists such that a minimal number of bins is used and given constraints on the contents of bins are satisfied. </P><P>In our example, there are 3 types of bins and 5 types of components. The bin types are red, blue, and green. The component types are glass, plastic, steel, wood, and copper. </P><P>The following constraints must hold for the contents of bins: </P><OL type="1"><LI><P>Capacity constraints: </P><OL type="a"><LI><P>Red bins can take at most 3 components, and at most 1 component of type wood.</P></LI><LI><P>Blue bins can take exactly 1 component.</P></LI><LI><P>Green bins can take at most 4 components, and at most 2 components of type wood.</P></LI></OL><P></P></LI><LI><P>Containment constraints (what can go into what): </P><OL type="a"><LI><P>Red bins can contain glass, wood, and copper.</P></LI><LI><P>Blue bins can contain glass, steel, and copper.</P></LI><LI><P>Green bins can contain plastic, wood, and copper.</P></LI></OL><P></P></LI><LI><P>Requirement and exclusion constraints applying to all bin types: </P><OL type="a"><LI><P>Wood requires plastic.</P></LI><LI><P>Glass excludes copper.</P></LI><LI><P>Copper excludes plastic.</P></LI></OL><P></P></LI></OL><P> </P><P>Compile a packing list for an order consisting of 1 glass component, 2 plastic components, 1 steel component, 3 wood components, and 2 copper components. The packing list should require as few bins as possible. </P></DIV><DIV class="unnumbered"><H3><A name="label112">Model</A></H3><P>One possibility for a model consists in having a variable for every component saying in which bin the component should be packed. The resulting model admits many symmetric solutions and does not lead to a satisfactory script. </P><P>We will use a dual model that has variables for bins but not for components. The model has a variable <IMG alt="{\it NbBins}" src="latex220.png"> saying how many bins are used to pack the order. The individual bins are then referred to as first, second, and so on bin. For every <IMG alt="i\in1\#{\it NbBins}" src="latex221.png"> we have 6 variables: </P><UL><LI><P><IMG alt="{\it Type}_i" src="latex222.png"> denoting the type of the <IMG alt="i" src="latex115.png">-th bin.</P></LI><LI><P><IMG alt="{\it Glass}_i" src="latex223.png"> denoting the number of glass components to be packed into the <IMG alt="i" src="latex115.png">-th bin.</P></LI><LI><P><IMG alt="{\it Plastic}_i" src="latex224.png"> denoting the number of plastic components to be packed into the <IMG alt="i" src="latex115.png">-th bin.</P></LI><LI><P><IMG alt="{\it Steel}_i" src="latex225.png"> denoting the number of steel components to be packed into the <IMG alt="i" src="latex115.png">-th bin.</P></LI><LI><P><IMG alt="{\it Wood}_i" src="latex226.png"> denoting the number of wood components to be packed into the <IMG alt="i" src="latex115.png">-th bin.</P></LI><LI><P><IMG alt="{\it Copper}_i" src="latex227.png"> denoting the number of copper components to be packed into the <IMG alt="i" src="latex115.png">-th bin.</P></LI></UL><P> Given these variables, the capacity and containment constraints are easy to express. The requirement and exclusion constraints are implications that can be expressed by means of reified constraints. </P><P>To reduce the size of the search tree, we exclude some of the symmetries in a packing list. We require that blue bins appear before red bins, and red bins appear before green bins. Moreover, if two consecutive bins have the same type, the first bin must contain at least as many glass components as the second bin.</P></DIV><DIV class="unnumbered"><H3><A name="label113">Distribution Strategy</A></H3><P>We will use a three-dimensional distribution strategy. First we distribute on <IMG alt="{\it NbBins}" src="latex220.png">, trying smaller values first. Then we distribute on the type variables <IMG alt="{\it Type}_1,\;{{\it
Type}_2,\;\ldots}" src="latex228.png"> with a naive strategy trying the values blue, red and green in this order. Finally, after the number and types of bins are determined, we distribute on the capacity variables </P><BLOCKQUOTE><P><IMG alt="{\it Glass}_1,\;
{\it Plastic}_1,\;
{\it Steel}_1,\;
{\it Wood}_1,\;
{\it Copper}_1,\;
{\it Glass}_2,\;
{\it Plastic}_2,\;
\ldots" src="latex229.png"></P></BLOCKQUOTE><P> with the standard first-fail strategy. </P></DIV><DIV class="unnumbered"><H3><A name="label114">Script</A></H3><P></P><DIV id="progbinpacking"><HR><P><A name="progbinpacking"></A></P><DL class="anonymous"><DD class="code"><CODE><SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">BinPacking</SPAN> Order}<BR> ComponentTypes = [glass plastic steel wood copper]<BR> MaxBinCapacity = 4<BR> </CODE><SPAN class="chunktitle"><SPAN class="chunkborder"><</SPAN><A href="node39.html#label115">Definition of IsBin</A><SPAN class="chunkborder">></SPAN></SPAN><CODE> <BR> </CODE><SPAN class="chunktitle"><SPAN class="chunkborder"><</SPAN><A href="node39.html#label116">Definition of IsPackList</A><SPAN class="chunkborder">></SPAN></SPAN><CODE> <BR> </CODE><SPAN class="chunktitle"><SPAN class="chunkborder"><</SPAN><A href="node39.html#label117">Definition of Match</A><SPAN class="chunkborder">></SPAN></SPAN><CODE> <BR> </CODE><SPAN class="chunktitle"><SPAN class="chunkborder"><</SPAN><A href="node39.html#label118">Definition of Distribute</A><SPAN class="chunkborder">></SPAN></SPAN><CODE> <BR><SPAN class="keyword">in</SPAN> <BR> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> PackList}<BR> {IsPackList PackList}<BR> {Match PackList Order} <BR> {Distribute PackList}<BR> <SPAN class="keyword">end</SPAN> <BR><SPAN class="keyword">end</SPAN></CODE></DD></DL><P class="caption"><STRONG>Figure 8.3:</STRONG> A script for the Bin Packing Problem.</P><HR></DIV><P> </P><P>The script is shown in <A href="node39.html#progbinpacking">Figure 8.3</A>. It takes as parameter the order for which a packing list is to be compiled. The statement </P><DL class="anonymous"><DD class="code"><CODE>{Browse <BR> {SearchOne <BR> {BinPacking <BR> order(glass:2 plastic:4 steel:3 wood:6 copper:4)}}}</CODE></DD></DL><P> will compute a packing list for the order that was given in the problem specification: </P><BLOCKQUOTE class="code"><CODE>[ b(copper:0 glass:0 plastic:0 steel:1 type:0 wood:0) <BR> b(copper:0 glass:0 plastic:0 steel:1 type:0 wood:0) <BR> b(copper:0 glass:0 plastic:0 steel:1 type:0 wood:0) <BR> b(copper:0 glass:2 plastic:0 steel:0 type:1 wood:0) <BR> b(copper:4 glass:0 plastic:0 steel:0 type:2 wood:0) <BR> b(copper:0 glass:0 plastic:1 steel:0 type:2 wood:2) <BR> b(copper:0 glass:0 plastic:1 steel:0 type:2 wood:2) <BR> b(copper:0 glass:0 plastic:2 steel:0 type:2 wood:2) ]</CODE></BLOCKQUOTE><P> </P><P>From the printout we can see that the script represents a packing list as a list of packed bins. The types of the bins are coded as numbers, where 0 is blue, 1 is red, and 2 is green. The packed bin </P><BLOCKQUOTE class="code"><CODE>b(copper:0 glass:0 plastic:1 steel:0 type:2 wood:2)</CODE></BLOCKQUOTE><P> has type green and contains 1 plastic and 2 wood components. </P><P>The procedure <CODE>{BinPacking Order}</CODE> introduces three defined constraints <CODE>IsBin</CODE>, <CODE>IsPackList</CODE>, and <CODE>Match</CODE>. It also defines a procedure <CODE>Distribute</CODE> implementing the distribution strategy. Given these procedures, the script itself is straightforward. </P><DIV class="apropos"><P class="margin"><CODE>IsBin</CODE></P><P> The definition of the procedure <CODE>{IsBin Bin}</CODE> appears in <A href="node39.html#progisbin">Figure 8.4</A>. It imposes constraints saying that <CODE>Bin</CODE> is a consistently packed bin. In fact, the procedure <CODE>{IsBin Bin}</CODE> implements all the capacity, containment, requirement, and exclusion constraints of the problem specification. The thread creation at the end of the procedure is needed so that the conditional does not block on the determination of <CODE>Type</CODE>. </P></DIV><P></P><DIV id="progisbin"><HR><P><A name="progisbin"></A></P><DL><DT><SPAN class="chunktitle"><SPAN class="chunkborder"><</SPAN><A name="label115">Definition of IsBin</A><SPAN class="chunkborder">>=</SPAN></SPAN></DT><DD class="code"><CODE><SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">IsBin</SPAN> Bin}<BR> [Blue Red Green] = [0 1 2]<BR> BinTypes = [Blue Red Green]<BR> Capacity = {FD<SPAN class="keyword">.</SPAN>int [1 3 4]} % <SPAN class="comment">capacity of Bin<BR></SPAN> Type = {FD<SPAN class="keyword">.</SPAN>int BinTypes} % <SPAN class="comment">type of Bin<BR></SPAN> Components <BR> [Glass Plastic Steel Wood Copper] = Components<BR><SPAN class="keyword">in</SPAN> <BR> Bin = b(type:Type glass:Glass plastic:Plastic<BR> steel:Steel wood:Wood copper:Copper)<BR> Components <SPAN class="keyword">:::</SPAN> 0<SPAN class="keyword">#</SPAN>MaxBinCapacity<BR> {FD<SPAN class="keyword">.</SPAN>sum Components <SPAN class="string">'=<:'</SPAN> Capacity}<BR> {FD<SPAN class="keyword">.</SPAN>impl Wood<SPAN class="keyword">>:</SPAN>0 Plastic<SPAN class="keyword">>:</SPAN>0 1} % <SPAN class="comment">wood requires plastic<BR></SPAN> {FD<SPAN class="keyword">.</SPAN>impl Glass<SPAN class="keyword">>:</SPAN>0 Copper<SPAN class="keyword">=:</SPAN>0 1} % <SPAN class="comment">glass excludes copper<BR></SPAN> {FD<SPAN class="keyword">.</SPAN>impl Copper<SPAN class="keyword">>:</SPAN>0 Plastic<SPAN class="keyword">=:</SPAN>0 1} % <SPAN class="comment">copper excludes plastic<BR></SPAN> <SPAN class="keyword">thread</SPAN> <BR> <SPAN class="keyword">case</SPAN> Type<BR> <SPAN class="keyword">of</SPAN> <SPAN class="keyword">!</SPAN>Red <SPAN class="keyword">then</SPAN> Capacity=3 Plastic=0 Steel=0 Wood<SPAN class="keyword">=<:</SPAN>1<BR> <SPAN class="keyword">[]</SPAN> <SPAN class="keyword">!</SPAN>Blue <SPAN class="keyword">then</SPAN> Capacity=1 Plastic=0 Wood=0<BR> <SPAN class="keyword">[]</SPAN> <SPAN class="keyword">!</SPAN>Green <SPAN class="keyword">then</SPAN> Capacity=4 Glass = 0 Steel=0 Wood<SPAN class="keyword">=<:</SPAN>2<BR> <SPAN class="keyword">end</SPAN> <BR> <SPAN class="keyword">end</SPAN> <BR><SPAN class="keyword">end</SPAN></CODE></DD></DL><P class="caption"><STRONG>Figure 8.4:</STRONG> The defined constraint <CODE>IsBin</CODE>.</P><HR></DIV><P> </P><DIV class="apropos"><P class="margin">implementing implicative constraints with conditionals</P><P> The conditional implements three implicative constraints. Implementing these implicative constraints with reified constraints would be much more expensive. For instance, the statement implementing the first implicative constraint would take the form </P><BLOCKQUOTE class="code"><CODE>{FD<SPAN class="keyword">.</SPAN>impl Type<SPAN class="keyword">=:</SPAN>Red<BR> ((Capacity<SPAN class="keyword">=:</SPAN>3) <SPAN class="keyword">+</SPAN> (Plastic<SPAN class="keyword">=:</SPAN>0) <BR> <SPAN class="keyword">+</SPAN> (Steel<SPAN class="keyword">=:</SPAN>0) <SPAN class="keyword">+</SPAN> (Wood<SPAN class="keyword">=<:</SPAN>1) <SPAN class="keyword">=:</SPAN> 4)<BR> 1}</CODE></BLOCKQUOTE><P> and thus create 7 propagators. In contrast, the implementation of all three implicative constraints with a single conditional creates at most one propagator. </P></DIV><P>The reified implementation <CODE>{FD<SPAN class="keyword">.</SPAN>impl A B 1}</CODE> of an implication <IMG alt="A\to B" src="latex230.png"> yields stronger propagation than the conditional implementation </P><BLOCKQUOTE class="code"><CODE><SPAN class="keyword">if</SPAN> A<SPAN class="keyword">==</SPAN>1 <SPAN class="keyword">then</SPAN> B=1 <SPAN class="keyword">else</SPAN> B=0 <SPAN class="keyword">end</SPAN></CODE></BLOCKQUOTE><P> since it will tell <CODE>A=0</CODE> once <CODE>B=0</CODE> is known. Given our distribution strategy, the backward propagation would not have much effect in our example. </P><DIV class="apropos"><P class="margin"><CODE>IsPackList</CODE></P><P> The procedure <CODE>{IsPackList Xs}</CODE> (see <A href="node39.html#progbinpacking.ispacklist">Figure 8.5</A>) imposes constraints saying that <CODE>Xs</CODE> is a consistent packing list ordered as specified in the description of the model. The thread creation prevents <CODE>IsPackList</CODE> from blocking on the determination of the list structure of <CODE>Xs</CODE>. </P><DIV id="progbinpacking.ispacklist"><HR><P><A name="progbinpacking.ispacklist"></A></P><DL><DT><SPAN class="chunktitle"><SPAN class="chunkborder"><</SPAN><A name="label116">Definition of IsPackList</A><SPAN class="chunkborder">>=</SPAN></SPAN></DT><DD class="code"><CODE><SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">IsPackList</SPAN> Xs}<BR> <SPAN class="keyword">thread</SPAN> <BR> {ForAll Xs IsBin}<BR> {ForAllTail Xs % <SPAN class="comment">impose order <BR></SPAN> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> Ys}<BR> <SPAN class="keyword">case</SPAN> Ys <SPAN class="keyword">of</SPAN> A<SPAN class="keyword">|</SPAN>B<SPAN class="keyword">|</SPAN>_ <SPAN class="keyword">then</SPAN> <BR> A<SPAN class="keyword">.</SPAN>type <SPAN class="keyword">=<:</SPAN> B<SPAN class="keyword">.</SPAN>type<BR> {FD<SPAN class="keyword">.</SPAN>impl A<SPAN class="keyword">.</SPAN>type<SPAN class="keyword">=:</SPAN>B<SPAN class="keyword">.</SPAN>type A<SPAN class="keyword">.</SPAN>glass<SPAN class="keyword">>=:</SPAN>B<SPAN class="keyword">.</SPAN>glass 1}<BR> <SPAN class="keyword">else</SPAN> <SPAN class="keyword">skip</SPAN> <BR> <SPAN class="keyword">end</SPAN> <BR> <SPAN class="keyword">end</SPAN>}<BR> <SPAN class="keyword">end</SPAN> <BR><SPAN class="keyword">end</SPAN></CODE></DD></DL><P class="caption"><STRONG>Figure 8.5:</STRONG> The defined constraint <CODE>IsPackList</CODE> for the Bin Packing Problem.</P><HR></DIV><P> </P></DIV><DIV class="apropos"><P class="margin"><CODE>Match</CODE></P><P> The procedure <CODE>{Match PackList Order}</CODE> (see <A href="node39.html#progbinpacking.match">Figure 8.6</A>) imposes constraints saying that the packing list <CODE>PackList</CODE> matches the order <CODE>Order</CODE>. Once more a thread creation is needed to prevent <CODE>Match</CODE> from blocking on the determination of the list structure of <CODE>PackList</CODE>. </P><DIV id="progbinpacking.match"><HR><P><A name="progbinpacking.match"></A></P><DL><DT><SPAN class="chunktitle"><SPAN class="chunkborder"><</SPAN><A name="label117">Definition of Match</A><SPAN class="chunkborder">>=</SPAN></SPAN></DT><DD class="code"><CODE><SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">Match</SPAN> PackList Order}<BR> <SPAN class="keyword">thread</SPAN> <BR> {ForAll ComponentTypes<BR> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> C}<BR> {FD<SPAN class="keyword">.</SPAN>sum {Map PackList <SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> B} B<SPAN class="keyword">.</SPAN>C <SPAN class="keyword">end</SPAN>} <SPAN class="string">'=:'</SPAN> Order<SPAN class="keyword">.</SPAN>C}<BR> <SPAN class="keyword">end</SPAN>}<BR> <SPAN class="keyword">end</SPAN> <BR><SPAN class="keyword">end</SPAN></CODE></DD></DL><P class="caption"><STRONG>Figure 8.6:</STRONG> The defined constraint <CODE>Match</CODE> for the Bin Packing Problem.</P><HR></DIV><P> </P></DIV><DIV class="apropos"><P class="margin"><CODE>Distribute</CODE></P><P> The procedure <CODE>{Distribute PackList}</CODE> implements the distribution strategy (see <A href="node39.html#progbinpacking.distribute">Figure 8.7</A>). It first computes a lower bound <CODE>min</CODE> for <CODE>NbBins</CODE> and then distributes naively on <CODE>NbBins</CODE>. After <CODE>NbBins</CODE> is determined, the variables <CODE>Types</CODE> and <CODE>Capacities</CODE> are constrained to the respective lists. Then the script first distributes on <CODE>Types</CODE> and afterwards on <CODE>Capacities</CODE>. </P><DIV id="progbinpacking.distribute"><HR><P><A name="progbinpacking.distribute"></A></P><DL><DT><SPAN class="chunktitle"><SPAN class="chunkborder"><</SPAN><A name="label118">Definition of Distribute</A><SPAN class="chunkborder">>=</SPAN></SPAN></DT><DD class="code"><CODE><SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">Distribute</SPAN> PackList}<BR> NbComps = {Record<SPAN class="keyword">.</SPAN>foldR Order Number<SPAN class="keyword">.</SPAN><SPAN class="string">'+'</SPAN> 0}<BR> Div = NbComps <SPAN class="keyword">div</SPAN> MaxBinCapacity<BR> Mod = NbComps <SPAN class="keyword">mod</SPAN> MaxBinCapacity<BR> Min = <SPAN class="keyword">if</SPAN> Mod<SPAN class="keyword">==</SPAN>0 <SPAN class="keyword">then</SPAN> Div <SPAN class="keyword">else</SPAN> Div<SPAN class="keyword">+</SPAN>1 <SPAN class="keyword">end</SPAN> <BR> NbBins = {FD<SPAN class="keyword">.</SPAN>int Min<SPAN class="keyword">#</SPAN>NbComps}<BR> Types<BR> Capacities<BR> <SPAN class="keyword">in</SPAN> <BR> {FD<SPAN class="keyword">.</SPAN>distribute naive [NbBins]}<BR> PackList = {MakeList NbBins} % <SPAN class="comment">blocks until NbBins is determined<BR></SPAN> Types = {Map PackList <SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> B} B<SPAN class="keyword">.</SPAN>type <SPAN class="keyword">end</SPAN>}<BR> Capacities = {FoldR PackList<BR> <SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> Bin Cs}<BR> {FoldR ComponentTypes <SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> T Ds} Bin<SPAN class="keyword">.</SPAN>T<SPAN class="keyword">|</SPAN>Ds <SPAN class="keyword">end</SPAN> Cs}<BR> <SPAN class="keyword">end</SPAN> <BR> nil}<BR> {FD<SPAN class="keyword">.</SPAN>distribute naive Types}<BR> {FD<SPAN class="keyword">.</SPAN>distribute ff Capacities}<BR> <SPAN class="keyword">end</SPAN></CODE></DD></DL><P class="caption"><STRONG>Figure 8.7:</STRONG> A distributor for the Bin Packing Problem.</P><HR></DIV><P> </P></DIV></DIV><DIV class="unnumbered"><H3><A name="label119">Exercises</A></H3><DIV class="exercise" id="reified.ex.e"><P><B>Exercise 8.5</B> (<A href="answers.html#label184">See solution</A>)</P><BLOCKQUOTE><P>The procedure <CODE>{IsPackList}</CODE> employs the statement </P><BLOCKQUOTE class="code"><CODE>{FD<SPAN class="keyword">.</SPAN>impl A<SPAN class="keyword">.</SPAN>type<SPAN class="keyword">=:</SPAN>B<SPAN class="keyword">.</SPAN>type A<SPAN class="keyword">.</SPAN>glass<SPAN class="keyword">>=:</SPAN>B<SPAN class="keyword">.</SPAN>glass 1}</CODE></BLOCKQUOTE><P> to post an implicative constraint. This will create 3 propagators. Implement the implicative constraint with a conditional that creates only 1 propagator.</P></BLOCKQUOTE></DIV></DIV></DIV><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node38.html#section.reified.srat"><< Prev</A></TD><TD><A href="node35.html">- Up -</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 (20110908185330)</SPAN></ADDRESS></BODY></HTML>
|