<!--
  - Authors:
  -   Christian Schulte <schulte@ps.uni-sb.de>
  -   Gert Smolka <smolka@dfki.de>
  -   Jörg Würtz
  -
  - 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.reified">
  <Title/Reified Constraints/

  <P>
In this section we will see a new class of
constraints called reified constraints.  Reified
constraints make it possible to express
constraints involving logical connectives such as
disjunction, implication, and negation.  Reified
constraints also make it possible to solve
overconstrained problems, for which only some of
the stated constraints can be satisfied.

<section id="section.reified.started">
  <title/Getting Started/

<para><title/reification of a constraint/
The <Em/reification of a constraint/ <math/C/ &wrt; a
variable <math/x/ is the constraint
<Math display>
(C \leftrightarrow x=1)
\;\land\;x\in0\#1
</Math>
where it is assumed that <math/x/ does not occur free
in <math/C/.

<P>
The operational semantics of a propagator for the
reification of a constraint <math/C/ &wrt; <math/x/ is
given by the following rules:
<list enum>
<item>
If the constraint store entails <math/x=1/, the
propagator for the reification reduces to a
propagator for <math/C/.
<item>
If the constraint store entails <math/x=0/, the
propagator for the reification reduces to a
propagator for <math/\neg C/}.
<item>
If a propagator for <math/C/ would realize that the
constraint store entails <math/C/, the propagator for
the reification tells <math/x=1/ and ceases to exist.
<item>
If a propagator for <math/C/ would realize that the
constraint store is inconsistent with <math/C/, the
propagator for the reification tells <math/x=0/ and
ceases to exist.
</list>

<P>
To understand these rules, you need to be
familiar with the definitions in
<Ptr to="section.constraints.propagation">.

<para><Title>0/1-variables</Title>
A <Em>0/1-variable</Em> is
a variable that is constrained to the finite
domain <math/0\#1/.  The control variables of reified
constraints are 0/1-variables.


<para><title/posting refied constraints/
Here are examples for statements creating
propagators for reified constraints:
<list>
<item>
<<(X<:Y)=B>> creates a propagator for the
reification of <Math/X<Y/ &wrt; <Math/B/.
<item>
<<(X+Y+Z=:0)=B>> creates a propagator for the
reification of <Math/X+Y+Z=0/ &wrt; <Math/B/.
<item>
<<(X\=:Y)=B>> creates a propagator for the
reification of <Math/X\neq Y/ &wrt; <Math/B/.
<item>
<<(X::0#10)=B>> creates a propagator for the
reification of <Math/X\in0\#10/ &wrt; <Math/B/.
<item>
<<{FD.reified.distance X Y '=:' Z B}>> creates a
propagator for the reification of
<Math/|X-Y|=Z/ &wrt; <Math/B/.
</list>


<para><title/expressing equivalences/
With reified constraints it is straightforward
to express
equivalences of constraints.  For instance, the
equivalence
<Math display/
X<Y\;\leftrightarrow\; X<Z
/
can be posted with the statement
<<<
X<:Y = X<:Z
>>>
This statement is a notational convenience for
<<<
local B in  
   X<:Y=B  X<:Z=B  
end
>>>
and creates 2 propagators for reified
constraints.

<para><title/Boolean connectives/
We can define the Boolean connectives
 (&eg;, conjunction or negation) by
associating 0 with false and 1 with true.  The
respective Boolean constraints can be posted by
means of the following procedures:
<list>
<item>
<<{FD.conj X Y Z}>> posts the constraint <Math/(X\land Y)=Z/.
<item>
<<{FD.disj X Y Z}>> posts the constraint <Math/(X\lor Y)=Z/.
<item>
<<{FD.impl X Y Z}>> posts the constraint <Math/(X\to Y)=Z/.
<item>
<<{FD.equi X Y Z}>> posts the constraint
<Math/(X\leftrightarrow Y)=Z/.
<item>
<<{FD.nega X Y}>> posts the constraint <Math/\neg X=Y/.
</list>

<subsection class=unnumbered>
  <title/Exercises/

<Exercise id="reified.ex.a">
Write a statement that posts the constraint
<Math display/
(X<Y\;\to\; X+Y=Z)
\;\;\leftrightarrow\;\;
(X\cdot Y=Z\;\lor\;Z\neq 5)
/
</Exercise>

<Answer to="reified.ex.a">
<<<{FD.impl X<:Y  X+Y=:Z} = {FD.disj  X*Y=:Z  Z\=:5}>>>
</Answer>

<Exercise id="reified.ex.b">
Write a procedure <<{Conj X Y Z}>> that posts the
constraints
<Math display/
(X\land Y)=Z
,\quad
X\in0\#1
,\quad
Y\in0\#1
/
<P>
The procedure should post the conjunction
<Math/(X\land Y)=Z/. by means of the reified form of
the infix operator <<=:>>.
<P>
Write analogous procedures <<Equi>> and <<Nega>>
posting equivalences and negations.
<P>
Write an analogous procedure <<Dis>> posting a
disjunction <Math/(X\lor Y)=Z/.  Use the reified form
of <code/<:/ to post the disjunction.
<P>
How would you write a procedure posting an
implication <Math/(X\to Y)=Z/?
</Exercise>

<Answer to="reified.ex.b">
<<<
proc {Conj X Y Z}
   X::0#1  Y::0#1
   (X+Y=:2) = Z
end
proc {Equi X Y Z}
   X::0#1  Y::0#1
   (X=:Y) = Z 
end
proc {Nega X Z}
   X::0#1
   (X=:0) = Z  
end
proc {Disj X Y Z}
   X::0#1  Y::0#1
   (X+Y>:0) = Z
end
proc {Impl X Y Z}
   X::0#1  Y::0#1
   (Y-X>=:0) = Z
end
>>>
</Answer>

</section>


<section id="section.reified.photo">
  <title/Example: Aligning for a Photo/

<P>
We will now see an overconstrained problem for
which it is impossible to satisfy all
constraints.  The problem specification will
distinguish between primary and secondary
constraints, and the goal is to find a solution
that satisfies all primary constraints and as
many of the secondary constraints as possible.

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

<P>
Betty, Chris, Donald, Fred, Gary, Mary, and Paul
want to align in one row for taking a photo.  Some
of them have preferences next to whom they want to
stand:
<list enum>
<item>
Betty wants to stand next to Gary and Mary.
<item>
Chris wants to stand next to Betty and Gary.
<item>
Fred wants to stand next to Mary and Donald.
<item>
Paul wants to stand next to Fred and Donald.
</list>
Obviously, it is impossible to satisfy all
preferences.  Can you find an alignment that
maximizes the number of satisfied preferences?

</subsection>

<subsection class=unnumbered>
  <title/Model/

<P>
The model has a variable <Math/A_p/ for every person,
where <Math/A_p/ stands for the position <Math/p/ takes in
the alignment.  Since there are exactly 7
persons, we have <Math/A_p\in 1\#7/ for every person
<Math/p/.  Moreover, we have <Math/A_p\neq A_q/ for every
pair <Math/p/,<Math/q/ of distinct persons.

The model has a variable <math/S_i\in0\#1/ for each of
the 8 preferences, where <math/S_i=1/ if and only if
the <math/i/-th preference is satisfied.  To express
this constraint, we constrain the control
variable <math/S/ of a preference ``person <math/p/ wants
to stand next to person <math/q/'' by means of the
reified constraint
<Math display/
(|A_p-A_q|=1
\;\leftrightarrow\;
S=1)
\;\land\;
S\in0\#1
/

<P>
Finally, there is a variable
<Math display/
{\it Satisfaction} \;=\; S_1\;+\;\ldots\;+\;S_8
/
denoting the number of satisfied preferences.  We
want to find a solution that maximizes the value
of <Math/{\it Satisfaction}/.

<P>
The experienced constraint programmer will note
that we can eliminate a symmetry by picking two
persons <Math/p/ and <Math/q/ and imposing the order
constraint <Math/A_p<A_q/.

</subsection>

<subsection class=unnumbered>
  <title/Distribution Strategy./

<P>
To maximize <Math/{\it Satisfaction}/, we employ a
two-dimensional distribution strategy, which first
distributes on <Math/{\it Satisfaction}/, trying the
values <Math/8,\,7,\,\ldots\,1/ in this order.  Once
<Math/{\it Satisfaction}/ is determined, we distribute
on the variables <Math/A_p/ using a first-fail strategy
that splits the domain of the selected variable.
</subsection>

<subsection class=unnumbered>
  <title/Script./

<P>
<figure id="ProgPhoto">
  <caption/A script for the Photo Puzzle./
<chunk class=anonymous><title/Photo/
proc {Photo Root}
   Persons       = [betty chris donald fred gary mary paul]
   Preferences   = [betty#gary betty#mary  chris#betty chris#gary
		    fred#mary  fred#donald paul#fred   paul#donald]
   NbPersons     = {Length Persons}
   Alignment     = {FD.record alignment Persons 1#NbPersons}
   Satisfaction  = {FD.decl} 
   proc {Satisfied P#Q S}
      {FD.reified.distance Alignment.P Alignment.Q '=:' 1 S}
   end
in
   Root = r(satisfaction: Satisfaction
	    alignment:    Alignment)
   {FD.distinct Alignment}
   {FD.sum {Map Preferences Satisfied} '=:' Satisfaction}
   Alignment.fred <: Alignment.betty     % breaking symmetries
   {FD.distribute generic(order:naive value:max) [Satisfaction]}
   {FD.distribute split Alignment}
end
</chunk>
</figure>


<P>
The script in <Ptr to=ProgPhoto> constrains
its root variable to a record
consisting of the number of satisfied preferences
and a record mapping the names of the persons to
their positions in the alignment.  The fields of
the record <<Alignment>> implement the variables
<Math/A_p/ of the model.

<para><title/<<Satisfied>>/
The script introduces the defined constraint
<<{Satisfied P#Q S}>>, 
which implements the reification of the constraint
``<<P>> stands next to <<Q>>'' &wrt; <<S>>.  

<P>
The statement
<<<
{FD.sum {Map Preferences Satisfied} '=:' Satisfaction}
>>>
constrains the variable <<Satisfaction>> to the
number of satisfied preferences.

<P id="page.reified.photoSol">
The statement <<{ExploreOne Photo}>>  will run the
script until a first solution is found.  The first
solution satisfies 6 preferences and looks as
follows:
<<<
6 # alignment(betty:5  chris:6  donald:1  fred:3 
              gary:7   mary:4   paul:2)
>>>
By construction of the script, this is the maximal
number of preferences that can be satisfied
simultaneously.
 </subsection>

<subsection class=unnumbered>
  <title/Exercises/

<Exercise id="reified.ex.c">
Modify the script such that the first solution
minimizes the number of preferences satisfied.
</Exercise>

<Answer to="reified.ex.c">
To minimize the value of <<Satisfaction>>, we
modify the distributor for <<Satisfaction>> such
that it tries smaller values first:
<<<
{FD.distribute generic(order:naive value:min) [Satisfaction]}
>>>
It turns out that the persons can be aligned such
that no preference is satisfied.
</Answer>


</section>



<section id="section.reified.srat">
  <title/Example: Self-referential Aptitude Test/

<P>
This example illustrates three issues: expressing
complex propositional formulas as reified
constraints, improving performance and
presentation by elimination of common
subconstraints, and using the symbolic constraint
posted by <<FD.element>>.

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

<p>
The self-referential aptitude test (which is taken from <ptr
to="Henz.96">) consists of 10
multiple choice questions, referred to as 1 to
10.  Each question allows for 5 possible answers,
referred to as a to e.  For each of the 50
possible answers, a condition is specified.  For
each question, exactly one of the conditions
associated with its possible answers must hold.
A solution of the test is a function assigning to
every question a letter such that the condition
selected by the assigned letter holds.  Here are
the questions and their possible answers:
<list enum>
<item>
The first question whose answer is b is question
(a)&nbsp;2; (b)&nbsp;3; (c)&nbsp;4; (d)&nbsp;5; (e)&nbsp;6.
<item>
The only two consecutive questions with identical
answers are questions (a)&nbsp;2 and 3; (b)&nbsp;3 and 4;
(c)&nbsp;4 and 5; (d)&nbsp;5 and 6; (e)&nbsp;6 and&nbsp;7.
<item>
The answer to this question is the same as the answer
to question (a)&nbsp;1; (b)&nbsp;2; (c)&nbsp;4; (d)&nbsp;7; (e)&nbsp;6.
<item>
The number of questions with the answer a is
(a)&nbsp;0; (b)&nbsp;1; (c)&nbsp;2; (d)&nbsp;3; (e)&nbsp;4.
<item>
The answer to this question is the same as the
answer to question (a)&nbsp;10; (b)&nbsp;9; (c)&nbsp;8; (d)&nbsp;7; (e)&nbsp;6.
<item>
The number of questions with answer a equals the
number of questions with answer (a)&nbsp;b; (b)&nbsp;c;
(c)&nbsp;d; (d)&nbsp;e; (e)&nbsp;none of the above.
<item>
Alphabetically, the answer to this question and
the answer to the following question are (a)&nbsp;4
apart; (b)&nbsp;3 apart; (c)&nbsp;2 apart; (d)&nbsp;1 apart;
(e)&nbsp;the same.
<item>
The number of questions whose answers are vowels
is (a)&nbsp;2; (b)&nbsp;3; (c)&nbsp;4; (d)&nbsp;5; (e)&nbsp;6.
<item>
The number of questions whose answer is a
consonant is (a)&nbsp;a prime; (b)&nbsp;a factorial; (c)
a square; (d)&nbsp;a cube; (e)&nbsp;divisible by 5.
<item>
The answer to this question is (a)&nbsp;a; (b)&nbsp;b;
(c)&nbsp;c; (d)&nbsp;d; (e)&nbsp;e.
</list>

<p>
To understand the test, verify that
<table>
<tr/<td/1:c/ <td/2:d/ <td/3:e/ <td/4:b/ <td/5:e// 
<tr/<td/6:e/ <td/7:d/ <td/8:c/ <td/9:b/ <td/10:a//
</table>
is a correct set of answers for the test.  In
particular, convince yourself that for every
question the remaining 4 possibilities to answer
it are falsified.  The script we are going to
write will prove that there is no other set of
correct answers.

</subsection>

<subsection class=unnumbered>
  <title/Model/

<P>
Our model has 0/1-variables <Math/A_i/, <Math/B_i/, <Math/C_i/,
and <Math/D_i/ for <Math/i\in1\#10/ such that:
<list enum>
<item>
<Math/A_i+B_i+C_i+D_i+E_i=1/.
<item>
<Math/A_i=1/ iff the answer to Question <Math/i/ is a.
<item>
<Math/B_i=1/ iff the answer to Question <Math/i/ is b.
<item>
<Math/C_i=1/ iff the answer to Question <Math/i/ is c.
<item>
<Math/D_i=1/ iff the answer to Question <Math/i/ is d.
<item>
<Math/E_i=1/ iff the answer to Question <Math/i/ is e.
</list>
To obtain a compact representation of the
questions, we also have variables <Math/Q_i\in1\#5/
for <Math/i\in1\#10/ such that
<table>
<tr/ 
<td/<math/Q_i=1\leftrightarrow A_i=1//
<td/<math/Q_i=2\leftrightarrow B_i=1///
<tr/ 
<td/<math/Q_i=3\leftrightarrow C_i=1//
<td/<math/Q_i=4\leftrightarrow D_i=1///
<tr/ 
<td/<math/Q_i=5\leftrightarrow E_i=1///
</table>

<P>
The first question can now be expressed by means
of five equivalences:
<Math display/
\begin{array}{rcl}
A_1
&ampersand;=&ampersand;
B_2
\\
B_1
&ampersand;=&ampersand;
(B_3\land (B_2=0))
\\
C_1
&ampersand;=&ampersand;
(B_4\land (B_2+B_3=0))
\\
D_1
&ampersand;=&ampersand;
(B_5\land (B_2+B_3+B_4=0))
\\
E_1
&ampersand;=&ampersand;
(B_6\land (B_2+B_3+B_4+B_5=0))
\end{array}
/
These equivalences can be expressed by reifying
the nested equality constraints.

<P>
The second question can be expressed with the
following constraints:
<Math display/
\begin{array}{rcl}
&ampersand;
Q_1\neq Q_2,\quad
Q_7\neq Q_8,\quad
Q_8\neq Q_9,\quad
Q_9\neq Q_10
\\
&ampersand;
A_2=(Q_2=Q_3),\quad
B_2=(Q_3=Q_4),\quad
C_2=(Q_4=Q_5)
\\
&ampersand;
D_2=(Q_5=Q_6),\quad
E_2=(Q_6=Q_7)
\end{array}
/

<P>
The third question can be expressed as follows:
<Math display/
\begin{array}{rcl}
&ampersand;
A_3=(Q_1=Q_3),\quad
B_3=(Q_2=Q_3),\quad
C_3=(Q_4=Q_3)
\\
&ampersand;
D_3=(Q_7=Q_3),\quad
E_3=(Q_6=Q_3)
\end{array}
/

<P>
The fourth question can be elegantly expressed with
the constraint
<Math display/
{\it element}(Q_4,\;(0,1,2,3,4)) =
\sum_{i=1}^{10}{A_i}
/
where the function <Math/{\it element}(k,x)/ yields
the <Math/k/-th component of the tuple <Math/x/.  

<p>
We choose
this formulation since Oz provides a propagator
<<FD.element>> for the constraint <Math/{\it
element}(k,x)=y/.

<para><title/reified membership constraints/
The nineth question can be expressed with the
following equations
<Math display/
\begin{array}{rcl}
S
&ampersand;=&ampersand;
\sum_{i=1}^{10}{(B_i+C_i+D_i)}
\\
A_9
&ampersand;=&ampersand;
(S\in\{2,3,5,7\})
\\
B_9
&ampersand;=&ampersand;
(S\in\{1,2,6\})
\\
C_9
&ampersand;=&ampersand;
(S\in\{0,1,4,9\})
\\
D_9
&ampersand;=&ampersand;
(S\in\{0,1,8\})
\\
E_9
&ampersand;=&ampersand;
(S\in\{0,5,10\})
\end{array}
/
where <Math/S/ is an existentially quantified
auxiliary variable.  This time we use reified
membership constraints of the form <Math/x\in D/.
</subsection>

<subsection class=unnumbered>
<title/Distribution Strategy/

<P>
We distribute on the variables
<Math/Q_1,\,Q_2\,\ldots/ using the standard first-fail
strategy.

</subsection>

<subsection class=unnumbered>
  <title/Script/

<P>
<figure id=ProgSRAT>
 <caption/A script for the self-referential aptitude test./
<chunk class=anonymous><title/SRAT/
proc {SRAT Q}
   proc {Vector V}  % V is a 0/1-vector of length 10
      {FD.tuple v 10 0#1 V} 
   end
   proc {Sum V S}   % S is the sum of the components of vector V
      {FD.decl S} {FD.sum V '=:' S} 
   end
   proc {Assert I U V W X Y}  
      A.I=U  B.I=V  C.I=W  D.I=X  E.I=Y 
   end
   A      = {Vector}              B    = {Vector}
   C      = {Vector}              D    = {Vector}        E    = {Vector}
   SumA   = {Sum A}               SumB = {Sum B}         SumC = {Sum C}  
   SumD   = {Sum D}               SumE = {Sum E}
   SumAE  = {Sum [SumA SumE]}     SumBCD = {Sum [SumB SumC SumD]}
in
   {FD.tuple q 10 1#5 Q}
   {For 1 10 1
    proc {$ I} {Assert I  Q.I=:1  Q.I=:2  Q.I=:3  Q.I=:4  Q.I=:5} end}
   %% 1
   {Assert 1 B.2
             {FD.conj B.3 (B.2=:0)}
             {FD.conj B.4 (B.2+B.3=:0)}
	     {FD.conj B.5 (B.2+B.3+B.4=:0)}
	     {FD.conj B.6 (B.2+B.3+B.4+B.5=:0)}}
   %% 2
   {Assert 2  Q.2=:Q.3  Q.3=:Q.4  Q.4=:Q.5  Q.5=:Q.6  Q.6=:Q.7}
   Q.1\=:Q.2  Q.7\=:Q.8  Q.8\=:Q.9  Q.9\=:Q.10
   %% 3
   {Assert 3  Q.1=:Q.3  Q.2=:Q.3  Q.4=:Q.3  Q.7=:Q.3  Q.6=:Q.3}
   %% 4
   {FD.element Q.4 [0 1 2 3 4] SumA}
   %% 5
   {Assert 5  Q.10=:Q.5  Q.9=:Q.5  Q.8=:Q.5  Q.7=:Q.5  Q.6=:Q.5}
   %% 6
   {Assert 6  SumA=:SumB  SumA=:SumC  SumA=:SumD  SumA=:SumE  _}
   %% 7
   {FD.element Q.7 [4 3 2 1 0] {FD.decl}={FD.distance Q.7 Q.8 '=:'}}
   %% 8
   {FD.element Q.8 [2 3 4 5 6] SumAE}
   %% 9
   {Assert 9 SumBCD::[2 3 5 7]  SumBCD::[1 2 6]     
             SumBCD::[0 1 4 9]  SumBCD::[0 1 8]
             SumBCD::[0 5 10]}
   %% 10
   {FD.distribute ff Q}
end
</chunk>
</figure>



<para class=apropos><title/elimination of
common subconstraints/
The script in <Ptr to=ProgSRAT> implements
the indexed variables <Math/A_i/, <Math/B_i/, <Math/C_i/, <Math/D_i/,
<Math/E_i/, and <Math/Q_i/ as tuples with 10 components
each.  The three procedures <<Vector>>, <<Sum>>,
and <<Assert>> make it more convenient to state
the constraints.  For each sum occurring in the
questions an auxiliary variable is introduced so
that the corresponding summation constraint needs
to be posted only once.  This elimination of
common subconstraints provides for a compact
formulation of the script and also improves its
performance.

<P>
The procedure <<{FD.element ?{K} ?{V} ?{X}}>> posts
a propagator for the constraint saying that ?{X}
is the ?{K}-th component of the vector ?{V}.

<p>
Note the use of <<FD.decl>> in the definition of
the procedure <<Sum>> and in the representation of
the seventh question.  Telling an initial domain
constraint for the respective variables is
necessary so that the propagators depending on
these variables can start their work.

</subsection>

<subsection class=unnumbered>
  <title/Exercises/

<Exercise id="reified.ex.d">
The script in <Ptr to=ProgSRAT> uses the
statement
<<<
{FD.element Q.7 [4 3 2 1 0] 
 {FD.decl}={FD.distance Q.7 Q.8 '=:'}}
>>>
to post the constraints for the seventh question.
It avoids one auxiliary variable by nesting two
equated procedure applications.  Give an
equivalent statement in which the auxiliary
variable is introduced and the nested procedure
applications are unfolded.
</Exercise>

<Answer to="reified.ex.d">
<<<
local Aux in
   {FD.decl Aux}
   {FD.distance Q.7 Q.8 '=:' Aux}
   {FD.element Q.7 [4 3 2 1 0] Aux}
end
>>>
</Answer>

</subsection>

</section>


<section id="section.reified.bin">
  <title/Example: Bin Packing/

<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.

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

<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>
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>
The following constraints must hold for the
contents of bins:
<list enum>
<item>
Capacity constraints:
<list enum>
<item>
Red bins can take at most 3 components, and at
most 1 component of type wood.
<item>
Blue bins can take exactly 1 component.
<item>
Green bins can take at most 4 components, and at
most 2 components of type wood.
</list>
<item>
Containment constraints (what can go into what):
<list enum>
<item>
Red bins can contain glass, wood, and copper.
<item>
Blue bins can contain glass, steel, and copper.
<item>
Green bins can contain plastic, wood, and copper.
</list>
<item>
Requirement and exclusion constraints applying to
all bin types:
<list enum>
<item>
Wood requires plastic.
<item>
Glass excludes copper.
<item>
Copper excludes plastic.
</list>
</list>

<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.
 
<subsection class=unnumbered>
  <title/Model/

<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>
We will use a dual model that has variables for
bins but not for components.  The model has a
variable <Math/{\it NbBins}/ 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 <Math/i\in1\#{\it NbBins}/ we have 6
variables:
<list>
<item>
<math/{\it Type}_i/ denoting the type of the <math/i/-th bin.
<item>
<math/{\it Glass}_i/ denoting the number of glass
components to be packed into the <math/i/-th bin.
<item>
<math/{\it Plastic}_i/ denoting the number of plastic
components to be packed into the <math/i/-th bin.
<item>
<math/{\it Steel}_i/ denoting the number of steel
components to be packed into the <math/i/-th bin.
<item>
<math/{\it Wood}_i/ denoting the number of wood
components to be packed into the <math/i/-th bin.
<item>
<math/{\it Copper}_i/ denoting the number of copper
components to be packed into the <math/i/-th bin.
</list>
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>
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.
</subsection>

<subsection class=unnumbered>
  <title/Distribution Strategy/

<P>
We will use a three-dimensional distribution
strategy.  First we distribute on <math/{\it NbBins}/,
trying smaller values first.  Then we distribute
on the type variables <math/{\it Type}_1,\;{{\it
Type}_2,\;\ldots}/ 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
<math display/
{\it Glass}_1,\;
{\it Plastic}_1,\;
{\it Steel}_1,\;
{\it Wood}_1,\;
{\it Copper}_1,\;
{\it Glass}_2,\;
{\it Plastic}_2,\;
\ldots
/
with the standard first-fail strategy.


<subsection class=unnumbered>
  <title/Script/

<P>
<figure id=ProgBinPacking>
  <caption/A script for the Bin Packing Problem./
<chunk class=anonymous><title/BinPacking/
fun {BinPacking Order}
   ComponentTypes = [glass plastic steel wood copper]
   MaxBinCapacity = 4
   <chunk.ref/Definition of IsBin/
   <chunk.ref/Definition of IsPackList/
   <chunk.ref/Definition of Match/
   <chunk.ref/Definition of Distribute/
in
   proc {$ PackList}
      {IsPackList PackList}
      {Match PackList Order}  
      {Distribute PackList}
   end
end
</chunk>
</figure>

<P>
The script is shown in
<Ptr to=ProgBinPacking>. It takes as parameter
the order for which a packing list is to be
compiled.  The statement
<chunk class=anonymous><title/{SearchOne BinPacking}/
{Browse 
 {SearchOne 
  {BinPacking 
   order(glass:2 plastic:4 steel:3 wood:6 copper:4)}}}
</chunk>
will compute a packing list for the order that
was given in the problem specification:
<<<
[ b(copper:0 glass:0 plastic:0 steel:1 type:0 wood:0) 
  b(copper:0 glass:0 plastic:0 steel:1 type:0 wood:0) 
  b(copper:0 glass:0 plastic:0 steel:1 type:0 wood:0) 
  b(copper:0 glass:2 plastic:0 steel:0 type:1 wood:0) 
  b(copper:4 glass:0 plastic:0 steel:0 type:2 wood:0) 
  b(copper:0 glass:0 plastic:1 steel:0 type:2 wood:2) 
  b(copper:0 glass:0 plastic:1 steel:0 type:2 wood:2) 
  b(copper:0 glass:0 plastic:2 steel:0 type:2 wood:2) ]
>>>

<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
<<<
b(copper:0 glass:0 plastic:1 steel:0 type:2 wood:2)
>>>
has type green and contains 1 plastic and 2 wood
components.

<P>
The procedure <<{BinPacking Order}>>  introduces
three defined constraints <<IsBin>>,
<<IsPackList>>, and <<Match>>.  It also defines a
procedure <<Distribute>>  implementing the
distribution strategy.  Given these procedures,
the script itself is straightforward.

<para class=apropos><title/<<IsBin>>/
The definition of the procedure <<{IsBin Bin}>>
appears in <Ptr to=ProgIsBin>.  It imposes constraints
saying that <<Bin>> is a consistently packed bin.
In fact, the procedure <<{IsBin Bin}>>  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 <<Type>>.

<P>
<figure id=ProgIsBin>
  <caption/The defined constraint <<IsBin>>./
<chunk><title/Definition of IsBin/
proc {IsBin Bin}
   [Blue Red Green] = [0 1 2]
   BinTypes         = [Blue Red Green]
   Capacity         = {FD.int [1 3 4]}     % capacity of Bin
   Type             = {FD.int BinTypes}    % type of Bin
   Components 
   [Glass Plastic Steel Wood Copper] = Components
in
   Bin = b(type:Type    glass:Glass  plastic:Plastic
	   steel:Steel  wood:Wood    copper:Copper)
   Components ::: 0#MaxBinCapacity
   {FD.sum Components '=<:' Capacity}
   {FD.impl Wood>:0  Plastic>:0 1}   % wood requires plastic
   {FD.impl Glass>:0  Copper=:0 1}   % glass excludes copper
   {FD.impl Copper>:0  Plastic=:0 1} % copper excludes plastic
   thread
      case Type
      of !Red then Capacity=3  Plastic=0  Steel=0  Wood=<:1
      [] !Blue then Capacity=1  Plastic=0  Wood=0
      [] !Green then Capacity=4  Glass = 0  Steel=0  Wood=<:2
      end
   end
end
</chunk>
</figure>


<para class=apropos><title/implementing implicative
constraints with conditionals/
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
<<<
{FD.impl Type=:Red
 ((Capacity=:3) + (Plastic=:0) 
     + (Steel=:0) + (Wood=<:1) =: 4)
 1}
>>>
and thus create 7 propagators.  In contrast, the
implementation of all three implicative
constraints with a single conditional creates
at most one propagator.

<P>
The reified implementation <<{FD.impl A B 1}>> of
an implication <Math/A\to B/ yields stronger
propagation than the conditional implementation
<<<
if A==1 then B=1 else B=0 end
>>>
since it will tell <<A=0>> once <<B=0>> is known.
Given our distribution strategy, the backward
propagation would not have much effect in our
example.

<para class=apropos><title/<<IsPackList>>/
The procedure <<{IsPackList Xs}>> (see <Ptr to="ProgBinPacking.IsPackList">) imposes constraints
saying that <<Xs>> is a consistent packing list
ordered as specified in the description of the
model.  The thread creation prevents
<<IsPackList>> from blocking on the determination
of the list structure of <<Xs>>.

<figure id="ProgBinPacking.IsPackList">
  <caption/The defined constraint <<IsPackList>> for the Bin Packing Problem./
<chunk><title/Definition of IsPackList/
proc {IsPackList Xs}
   thread
      {ForAll Xs IsBin}
      {ForAllTail Xs  % impose order 
       proc {$ Ys}
	  case Ys of A|B|_ then
	     A.type =<: B.type
	     {FD.impl A.type=:B.type  A.glass>=:B.glass  1}
	  else skip 
	  end
       end}
   end
end
</chunk>
</figure>

<para class=apropos><title/<<Match>>/
The procedure <<{Match PackList Order}>> (see <Ptr to="ProgBinPacking.Match">)
 imposes constraints saying
that the packing list <<PackList>> matches the
order <<Order>>.  Once more a thread creation is
needed to prevent <<Match>>  from blocking on the
determination of the list structure of
<<PackList>>.

<figure id="ProgBinPacking.Match">
  <caption/The defined constraint <<Match>> for the Bin Packing Problem./
<chunk><title/Definition of Match/
proc {Match PackList Order}
   thread
      {ForAll ComponentTypes
       proc {$ C}
	  {FD.sum {Map PackList fun {$ B} B.C end} '=:' Order.C}
       end}
   end
end
</chunk>
</figure>

<para class=apropos><title/<<Distribute>>/
The procedure <<{Distribute PackList}>>
 implements the
distribution strategy (see <Ptr to="ProgBinPacking.Distribute">).  It
first computes a lower 
bound <<min>> for <<NbBins>> and then distributes
naively on <<NbBins>>.  After <<NbBins>> is
determined, the variables <<Types>> and
<<Capacities>> are constrained to the respective
lists.  Then the script first distributes on
<<Types>> and afterwards on <<Capacities>>.

<figure id="ProgBinPacking.Distribute">
  <caption/A distributor for the Bin Packing Problem./
<chunk><title/Definition of Distribute/
   proc {Distribute PackList}
      NbComps = {Record.foldR Order Number.'+' 0}
      Div     = NbComps div MaxBinCapacity
      Mod     = NbComps mod MaxBinCapacity
      Min     = if Mod==0 then Div else Div+1 end
      NbBins  = {FD.int Min#NbComps}
      Types
      Capacities
   in
      {FD.distribute naive [NbBins]}
      PackList   = {MakeList NbBins} % blocks until NbBins is determined
      Types      = {Map PackList fun {$ B} B.type end}
      Capacities = {FoldR PackList
		    fun {$ Bin Cs}
		       {FoldR ComponentTypes fun {$ T Ds} Bin.T|Ds end Cs}
		    end
		    nil}
      {FD.distribute naive Types}
      {FD.distribute ff Capacities}
  end
</chunk>
</figure>

<subsection class=unnumbered>
  <title/Exercises/

<Exercise id="reified.ex.e">
The procedure <<{IsPackList}>> employs the
statement
<<<
{FD.impl A.type=:B.type A.glass>=:B.glass 1}
>>>
to post an implicative constraint.  This will
create 3 propagators.  Implement the implicative
constraint with a conditional that creates only 1
propagator.
</Exercise>

<Answer to="reified.ex.e">
<<<
thread
   if A.type==B.type then 
      A.glass >=: B.glass
   end
end
>>>
</Answer>

<![ %EXTRA; [
<section><title/NONE/
<p>
<chunk><title/EXAMPLES/
%%%
%%% Chapter: Reified Constraints
%%%

%%
%% Example: Aligning for a Photo
%%

declare
<chunk.ref/Photo/

{ExploreOne Photo}



%%
%% Example:  Self-referential Aptitude Test
%%

declare
<chunk.ref/SRAT/

{ExploreOne SRAT}



%%
%% Example: Bin Packing
%%

declare
<chunk.ref/BinPacking/

<chunk.ref/{SearchOne BinPacking}/



</chunk>
]]>

</chapter>




