<!--
  - Authors:
  -   Christian Schulte <schulte@ps.uni-sb.de>
  -   Gert Smolka <smolka@dfki.de>
  -   Jörg Würtz
  -
  - Contributors:
  -   Daniel Simon <dansim@ps.uni-sb.de>
  -   Andy Walter <anwalt@ps.uni-sb.de>
  -   
  - Copyright:
  -   Christian Schulte, 1998
  -   Gert Smolka, 1998
  -   Jörg Würtz, 1997
  -
  - Last change:
  -   $Date$ by $Author$
  -   $Revision$
  -
  - This file is part of Mozart, an implementation
  - of Oz 3
  -    http://www.mozart-oz.org
  -
  - See the file "LICENSE" or
  -    http://www.mozart-oz.org/LICENSE.html
  - for information on usage and redistribution
  - of this file, and for a DISCLAIMER OF ALL
  - WARRANTIES.
  -
  -->

<chapter id="chapter.packing">
  <title/Packing Problems/

<p>
In this chapter we show how finite domain constraints can be used to
solve packing problems. The example features symbolic constraints and a
nontrivial distribution strategy. 

<section id="section.packing.tiling">
  <title/Square Tiling/

<subsection class=unnumbered>
  <title/Problem Specification/

<p>
Given is a large square and a set of smaller squares which all have to
be placed in the larger square (called the <def/target square/) such
that no space of the larger square remains unoccuppied. No pair of small
squares may overlap. We will consider only problems where the area of
the target square equals the sum of the areas of the smaller squares.

<subsection class=unnumbered>
  <title/Model/

<p>
We will use a model that has two variables for the coordinates of the
lower left corner of a smaller square to place. Let <math/x_i/ be the
coordinate in <math/x/ and <math/y_i/ the coordinate in
<math/y/-direction.  We call the size of a square the length of a
single edge.  Let <math/S/ be the size of the target
square. If <math/s_i/ is the size of a smaller square, the domains of
the corresponding variables are <math/0\#(S-s_i)/.

<p>
The constraint that two small squares with coordinates <math/x_i,y_i/
and <math/x_j,y_j/ and sizes <math/s_i/ and <math/s_j/, respectively,
must not overlap can be stated by the following disjunction.  
<math display/
x_i + s_i \leq x_j \;\vee\; x_j + s_j \leq x_i \;\vee\; y_i +
s_i \leq s_j \;\vee\; y_j+s_j \leq y_i / 
One of the first two clauses
is true if the squares do not overlap in <math/x/-direction and one of
the last two clauses is true if the squares do not overlap in
<math/y/-direction. 

<p>
Because the propagation of the constraints introduced so far is rather
weak, we add redundant constraints to the model. 
Assume <math/n/ smaller squares to be given. Then, for every point in
<math/x/-direction (and for every point in <math/y/-direction) the sum of square sizes
which overlap this point must not be larger than the size of the target
square:
<math display/\forall i \in \{0,\ldots,S\}:\  S \geq 
\sum\limits_{j\in
\{1,\ldots,n\},\ x_j \leq i < x_j+s_j} s_i/
and analogously for every point in <math/y/-direction. Because for our problems
no place of the target square must be unoccupied, we can impose the even
stronger constraint 
<math display/\forall i \in \{0,\ldots,S\}:\  S = \sum\limits_{j\in
\{1,\ldots,n\},\ x_j \leq i < x_j+s_j} s_i/.


<subsection class=unnumbered id="section.packing.tiling.distribution">
  <title/Distribution Strategy/

<p>
To solve the problem we employ a special distribution strategy. We
determine all coordinates of a direction before we consider the other
direction. Assume that we first consider the <math/x/-direction. We
then compute the smallest possible <math/x/-position <math/{\it pos}/
to place a small square. Now we try successively to place an
<math/i/-th square on that position by distributing with <math/x_i =
{\it pos}/ and <math/x_i > {\it pos}/. We try the largest square first
to be placed because this should lead to a larger reduction of the
search space than to choose a smaller square.

<subsection class=unnumbered>
  <title/Script/

<p>
A script is shown in <Ptr to="figPackingFig">. Two example problems
are shown in <Ptr to="fig.packEx"> and are available through the
variable <<Problems>>. The script extracts the problem to solve and
creates propagators for the constraints described above. <p>

<figure id="figPackingFig">
<caption/A script for the packing problem./
<<<
fun {SquareTiling Problems}
   fun {GetComp ItemList What}
      {Map ItemList fun {$ S} S.What end}
   end
   fun {CreateSquares Problem}
      Squares = Problem.s
      Size    = Problem.size
   in 
      {FoldL {Arity Squares}
       fun{$ In Square}
	  S = Squares.Square
       in 
	  square(x:    {FD.int 0#Size-S}  
		 y:    {FD.int 0#Size-S}
		 size: S
		 name: Square)|In
       end nil}
   end
   proc {NoOverlap Squares}
      Sizes = {GetComp Squares size}
   in
      {FD.distinct2 {GetComp Squares x} Sizes {GetComp Squares y} Sizes}
   end
   proc {Capacity Squares Size}
      Names  = {Map Squares fun {$ S} S.name end}
      Dur    = {MakeRecord d Names}
      StartX = {MakeRecord s Names}
      StartY = {MakeRecord s Names}
   in
      {ForAll Squares proc {$ S}
			 N = S.name in 
			 StartX.N = S.x
			 StartY.N = S.y
			 Dur.N    = S.size
		      end}
      {FD.schedule.cumulative   [Names] StartX Dur Dur [Size]}
      {FD.schedule.cumulative   [Names] StartY Dur Dur [Size]}      
      {FD.schedule.cumulativeUp [Names] StartX Dur Dur [Size]}
      {FD.schedule.cumulativeUp [Names] StartY Dur Dur [Size]}      
   end
   fun {SortSquares Problem}
      {Sort {CreateSquares Problem} fun {$ X Y} X.size > Y.size end}
   end
   proc {Distribute Ls}  {\it see Figure~\ref{DistTiling}}   end
in 
   fun {$ P}
      Problem = Problems.P
   in 
      proc {$ Squares}
	 Squares = {SortSquares Problem}
	 {NoOverlap Squares}
	 {Capacity Squares Problem.size}
         {Distribute {GetComp Squares y}}
         {Distribute {GetComp Squares x}}
      end
   end
end
>>>
</figure>

<p>
The constraint that two squares must not overlap is imposed by the
propagator <<FD.distinct2>>. The redundant constraint is imposed by the
procedure <<Capacity>>. The propagator <<FD.schedule.cumulative>> imposes
the constraint
<math display/\forall i \in \{0,\ldots,S\}:\  S \geq 
\sum\limits_{j\in
\{1,\ldots,n\},\ x_j \leq i < x_j+s_j} s_i/
whereas the propagator <<FD.schedule.cumulativeUp>> imposes the
constraint 
<math display/\forall i \in \{0,\ldots,S\}:\  S \leq 
\sum\limits_{j\in
\{1,\ldots,n\},\ x_j \leq i < x_j+s_j} s_i./

<exercise id="packing.ex.a">
Write a procedure which does not use <<FD.distinct2>> to implement the
constraint that two squares must not overlap. 
</exercise>

<answer to="packing.ex.a">
We use reified constraints to implement the procedure. 
<<<
proc {NoOverlapNaive Squares}
   {ForAllTail Squares
    proc {$ S1|Ss}
       {ForAll Ss
	proc {$ S2}
	   (S1.x + S1.size =<: S2.x) +
	   (S2.x + S2.size =<: S1.x) +
	   (S1.y + S1.size =<: S2.y) +
	   (S2.y + S2.size =<: S1.y) >=: 1
        end}
    end}
end
>>>
</answer>

<exercise id="packing.ex.b">
Write a procedure which does not <<FD.schedule.cumulative>> or
<<FD.schedule.cumulativeUp>> to implement the redundant constraints. 
</exercise>

<answer to="packing.ex.b">
<<<
local
   proc {Impose Squares Size Sizes Axis}
      {Loop.for 0 Size-1 1
       proc {$ Pos}
	  Bs={Map Squares fun {$ S}
			     S.Axis :: {Max 0 Pos-S.size+1}#Pos
			  end}
       in 
	  {FD.sumC Sizes Bs '=:' Size}
       end}
   end
in 
   proc {CapacityNaive Squares Size}
      Sizes = {GetComp Squares size}
   in
      {Impose Squares Size Sizes x}
      {Impose Squares Size Sizes y}
   end
end
>>>
Note that the reified
domain constraint <<S.Axis :: &ellipsis;>> considers holes in domains
for propagation. 
</answer>


<p>
<figure id="fig.packEx">
<caption/Two example problems./
<<<
Problems = p( r(size:112 z:3
		s: sizes(a:50 b:42 c:37 d:35 e:33 f:29 g:27 h:25
			 i:24 j:19 k:18 l:17 m:16 n:15 o:11
			 p:9 q:8 r:7 s:6 t:4 u:2))
	      r(size:175 z:2
		s: sizes(a:81 b:64 c:56 d:55 e:51 f:43 g:39 h:38 i:35
			 j:33 k:31 l:30 m:29 n:20 o:18 p:16 q:14 r:9
			 s:8 t:5 u:4 v:3 w:2 x:1))
	    )
>>>
</figure>

<p>
The distributor is shown in Figure&nbsp;<Ptr
to="fig.DistTiling">. Note that the distributor is applied to the list
of smaller squares ordered by decreasing size. The distributor
preserves this ordering while determining coordinates for squares.

<p>
A solution for the first problem can be obtained by the statement
<<<
{ExploreOne {{SquareTiling Problems} 1}}
>>>

<figure id="fig.DistTiling">
<caption/A distribution strategy/
<<<
local
   proc {SelectSquare Ls Minimum Tried}
      case Ls of L|Lr then
         case {IsDet L} then
            {Distribute {Append {Reverse Tried} Lr}}
         else
	    choice L = Minimum
	    then {Distribute {Append {Reverse Tried} Lr}}
	    [] L >: Minimum
	    then {SelectSquare Lr Minimum L|Tried}
            end
         end
      else fail
      end
   end
in 
   proc {Distribute Ls}
      choice
	 case Ls of L|Lr then
	    Minimum = {FoldL Lr fun {$ I X}
				   {Min I {FD.reflect.min X}}
				end {FD.reflect.min L}}
         in
            {SelectSquare Ls Minimum nil}
         else skip
         end
      end
   end
end
>>>
</figure>

</chapter>

