<!--
  - 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.bab>
<title/Branch and Bound/<p>

In this chapter we focus on computing an optimal
solution according to a given cost function.
While we have searched for optimal solutions
already in <Ptr to="section.reified.photo"> and
<Ptr to="section.reified.bin">, we have used a
rather ad-hoc strategy there. This strategy lacks
generality and does not provide either for a proof
of optimality.
<p>

<para><title/branch and bound/
In this chapter we introduce a general schema to compute an optimal
solution according to an arbitrary cost function and show how it is
available in Oz. This schema is called <def/branch and bound/ and is available 
by  procedures like <<ExploreBest>> (see <Ptr.extern to="ozdoc:explorer"> and <Ptr.extern to="ozdoc:system"
key="chapter.search"> for more
search engines). A typical application of <<ExploreBest>> for a script
<<Script>> 
looks like
<<<
{ExploreBest Script Order}
>>>
The branch and bound schema works as follows. When a solution of
<<Script>> is found, all the remaining alternatives in the search tree
are constrained to be <def/better/ with respect to an order available
through the procedure <<Order>>.  Usually <<Order>> applies a cost
function to its arguments and creates a propagator imposing
the ordering. The first argument of <<Order>> is the previous solution,
and the second argument is an alternative solution we are searching for.


<section id="section.bab.align">
<title/Example: Aligning for a Photo, Revisited/

<p>
In <Ptr to="section.reified.photo"> we have searched for a solution of
the alignment problem which satisfies the maximal number of
preferences. To this aim we have introduced a variable which counts the
number of satisfied preferences. By distributing this variable with its
maximal value first, we have guaranteed that the first solution found
is indeed the optimal one.

<p>
In this section we replace this ad-hoc approach by branch
and bound. We first restate the script for the problem by omitting the
distribution code for the variable summing up the satisfied
preferences. The resulting script is shown in
<Ptr to="ProgPhotoRevised">.

<Figure id="ProgPhotoRevised">
<caption/The revised script for the Photo Puzzle./
<chunk class=anonymous><title/RevisedPhoto/
proc {RevisedPhoto 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 split Alignment}
end
</chunk>
</figure>

<p>
Next we define an ordering procedure which states that
the overall sum of satisfied preferences in an alternative solution must
be strictly greater than the corresponding sum in a previous solution:
<chunk class=anonymous><title/PhotoOrder/
proc {PhotoOrder Old New}
   Old.satisfaction <: New.satisfaction
end	
</chunk>
The optimal solution can be found with the statement
<chunk class=anonymous><title/{ExploreBest RevisedPhoto}/
{ExploreBest RevisedPhoto PhotoOrder}
</chunk>
We obtain the same solution as in
<Ptr to="page.reified.photoSol">. But now only 141 choice nodes are
needed to find the optimal solution whereas 219 choice nodes were needed
in <Ptr to="section.reified.photo">. Furthermore, branch and bound allows
us to prove in an efficient way that the last solution found is really
the optimal one. The full search tree (including the proof of
optimality) contains 169 choice nodes; still less than for the search
for the best solution with the ad-hoc method. If we inspect the
solutions, we observe that the first solution satisfies only a single
preference. By imposition of the ordering procedure by the search
engine, the next found solution must satisfy more preferences. Indeed,
the second solution satisfies two preferences. Following this approach we
finally arrive at the optimal solution with six satisfied preferences.
</section>

<section id="section.bab.warehouses">
<title/Example: Locating Warehouses/<p>

This example features branch and bound to compute an optimal solution, a
non-trivial distribution strategy and symbolic constraints. 

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

<p>
Assume a company which wants to construct warehouses
to supply stores with goods. Each warehouse to be constructed would have
a certain capacity defining the largest number of stores which can be
supplied by this warehouse.  For the construction of a warehouse we have
fixed costs. The costs for transportation from a warehouse to a store
vary depending on the location of the warehouse and the supplied store. The aim
is to determine which warehouses should be constructed and which stores
should be supplied by the constructed warehouses such that the overall costs
are minimized.

<p>
We assume the fixed costs of building a warehouse to be 50. We furthermore
assume 5 warehouses W1 through W5 and 10 stores Store1 through Store10.
The capacities of the warehouses are shown in <Ptr to="table.BAB.caps">.
The costs to supply a store by a warehouse are shown in
<Ptr to="table.BAB.costs">.


<figure id="table.BAB.caps">
<caption/Capacities of warehouses./
<table>
  <tr/ <td/<p.silent/&nbsp;// 
       <td/<math/W_1// <td/<math/W_2// 
       <td/<math/W_3// <td/<math/W_4//
       <td/<math/W_5///
  <tr/ <td/Capacity/ 
       <td/1/ <td/4/ 
       <td/2/ <td/1/
       <td/3//
</table>
</figure>


<figure id="table.BAB.costs">
<caption/Costs for supplying stores./
<table>
  <tr/ <td/<p.silent/&nbsp;// 
       <td/<math/W_1// <td/<math/W_2// 
       <td/<math/W_3// <td/<math/W_4//
       <td/<math/W_5///
  <tr/ <td/<math/{\it Store}_1// 
       <td/36/ <td/42/ <td/22/ <td/44/ <td/52//
  <tr/ <td/<math/{\it Store}_2// 
       <td/49/ <td/47/ <td/134/ <td/135/ <td/121//
  <tr/ <td/<math/{\it Store}_3// 
       <td/121/ <td/158/ <td/117/ <td/156/ <td/115//
  <tr/ <td/<math/{\it Store}_4// 
       <td/8/ <td/91/ <td/120/ <td/113/ <td/101//
  <tr/ <td/<math/{\it Store}_5// 
       <td/77/ <td/156/ <td/98/ <td/135/ <td/11//
  <tr/ <td/<math/{\it Store}_6// 
       <td/71/ <td/39/ <td/50/ <td/110/ <td/98//
  <tr/ <td/<math/{\it Store}_7// 
       <td/6/ <td/12/ <td/120/ <td/98/ <td/93//
  <tr/ <td/<math/{\it Store}_8// 
       <td/20/ <td/120/ <td/25/ <td/72/ <td/156//
  <tr/ <td/<math/{\it Store}_9// 
       <td/151/ <td/60/ <td/104/ <td/139/ <td/77//
  <tr/ <td/<math/{\it Store}_{10}// 
       <td/79/ <td/107/ <td/91/ <td/117/ <td/154//
</table>
</figure>

<subsection class=unnumbered>
<title/Model/

<p>
We assume that the costs are given in the matrix <math/CostMatrix/ defined by
<Ptr to="table.BAB.costs">. 
For the model of this problem we introduce the following variables.
<p>
<list>
<item> <math/{\it Open}_i, 1 \leq i \leq 5/, with domain <math/0\#1/ such that
<math/{\it Open}_i=1/ if warehouse <math/W_i/ does supply at least one
store. 
<item> <math/{\it Supplier}_i, 1 \leq i \leq 10/, with domain <math/1\#5/ such that
<math/{\it Supplier}_i = j/ if store <math/{\it Store_i}/ is supplied  by
warehouse <math/W_j/. 
<item> <math/{\it Cost}_i, 1 \leq i \leq 10/, such that the domain of <math/{\it
Cost}_i/ is defined by the row <math/{\it CostMatrix}_i/. The variable <math/{\it
Cost}_i/ denotes the costs of supplying store <math/{\it Store}_i/ by
warehouse <math/W_{{\it Supplier}_i}/, &ie;, <math/{\it Cost}_i = {\it
CostMatrix}_{i,{\it Supplier}_i}/.
</list>

<p>
We have the additional constraint that the capacity of the warehouses
must not be exceeded. To this aim we introduce auxiliary variables <math/{\it
Supplies}_{i,j}/ with the domain <math/0\#1/ as follows. 
<math display/\forall i \in \{1,\ldots,5\} \forall  j \in \{1,\ldots, 10\}:\ ({\it Supplies}_{i,j} = 1)
\leftrightarrow ({\it Supplier_j} = i)/

The capacity constraints can then be stated with
<math display/\forall i \in \{1, \ldots, 5\}:\ {\it Cap}_i \geq
\sum\limits_{j=1}^{10}{\it Supplies}_{i,j}/
where <math/{\it Cap}_i/ is defined according to <Ptr to="table.BAB.caps">.

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

<p>
There are several possibilities to define a distribution strategy for
this problem. 

<para class=apropos><title/least regret/
We choose to determine the variables <math/{\it Cost}_i/ by
distribution. Because no entry in a row of the cost matrix occurs twice,
we immediately know which store is supplied by which warehouse. We
select the variable <math/{\it Cost}_i/ first for which the difference
between the smallest possible value and the next higher value is
maximal. Thus, decisions are made early in the search tree where the
difference between two costs by different suppliers are maximal. The
distribution strategy will try the minimal value in the domain of <math/{\it
Cost}_i/ first.  In Operations Research this strategy is known as the
principle of <def/least regret/.

<subsection class=unnumbered>
<title/Script/

<p>
The script in <Ptr to="program.Warehouse"> constrains its root
variable to a record containing the supplying warehouse for each store,
the costs for each store to be supplied by the corresponding warehouse
and the total costs.

<p>
The statement
<<<
{FD.element Supplier.St CostMatrix.St Cost.St}
>>>
connects the costs to supply a store with the supplier. Because no
element in a row of the cost matrix occurs twice, the supplier for a
store is known if its costs are determined and vice versa. Through this
statement the constraint <math/{\it Cost}_i = {\it
CostMatrix}_{i,{\it Supplier}_i}/ is imposed.

<p>
A propagator for the constraint that the capacity of a
warehouse is not exceeded can be created by the statement 
<<<
{FD.atMost Capacity.S Supplier S}
>>>

<p>
The statement 
<<<
Open.S = {FD.reified.sum {Map Stores fun {$ St} 
          Supplier.St =: S end} '>:' 0}
>>>

guarantees that a variable <math/{\it Open}_i/ in the model is constrained to
1 if warehouse <math/W_i/ supplies at least one store.

<p>
The first solution of the problem can be found with the statement
<chunk class=anonymous><title/{ExploreOne WareHouse}/
{ExploreOne WareHouse}
</chunk>

<p>
To compute the solution with minimal costs we define the following
ordering relation. 
<chunk class=anonymous><title/WareHouseOrder/
proc {Order Old New} 
   Old.totalCost >: New.totalCost 
end
</chunk>

<P>
The optimal solution with total cost 604 can now be computed with
<chunk class=anonymous><title/{ExploreBest WareHouse}/
{ExploreBest WareHouse Order}
</chunk>


<figure id="program.Warehouse">
<caption/A script for the warehouse problem./<p>

<chunk class=anonymous><title/WareHouse/
Capacity   = supplier(3 1 4 1 4)
CostMatrix = store(supplier(36 42 22 44 52) 
		   supplier(49 47 134 135 121) 
		   supplier(121 158 117 156 115) 
		   supplier(8 91 120 113 101) 
		   supplier(77 156 98 135 11) 
		   supplier(71 39 50 110 98) 
		   supplier(6 12 120 98 93) 
		   supplier(20 120 25 72 156) 
		   supplier(151 60 104 139 77) 
		   supplier(79 107 91 117 154))
BuildingCost = 50
fun {Regret X}
   M = {FD.reflect.min X} 
in 
   {FD.reflect.nextLarger X M} - M
end
proc {WareHouse X}
   NbSuppliers = {Width Capacity}
   NbStores    = {Width CostMatrix}
   Stores      = {List.number 1 NbStores 1}
   Supplier    = {FD.tuple store NbStores 1#NbSuppliers}
   Open        = {FD.tuple supplier NbSuppliers 0#1}
   Cost        = {FD.tuple store NbStores 0#FD.sup}
   SumCost     = {FD.decl} = {FD.sum Cost '=:'}
   NbOpen      = {FD.decl} = {FD.sum Open '=:'}
   TotalCost   = {FD.decl}
in
   X = plan(supplier:Supplier cost:Cost totalCost:TotalCost)
   TotalCost =: SumCost + NbOpen*BuildingCost
   {For 1 NbStores 1
    proc {$ St}
       Cost.St :: {Record.toList CostMatrix.St}
       {FD.element Supplier.St CostMatrix.St Cost.St}
    end}
   {For 1 NbSuppliers 1
    proc {$ S} 
       {FD.atMost Capacity.S Supplier S}
       Open.S = {FD.reified.sum {Map Stores fun {$ St} 
					       Supplier.St =: S 
					    end} '>:' 0}
    end}
   {FD.distribute
    generic(order: fun {$ X Y} {Regret X} > {Regret Y} end)
    Cost}
end
</chunk>
</figure>
</section>

<![ %EXTRA; [
<section><title/NONE/
<p>
<chunk><title/EXAMPLES/
%%%
%%% Chapter: Branch and Bound
%%%

%%
%% Example: Aligning for a Photo, Revisited
%%

declare
<chunk.ref/RevisedPhoto/

declare
<chunk.ref/PhotoOrder/

<chunk.ref/{ExploreBest RevisedPhoto}/



%%
%% Example: Locating Warehouses
%%

declare
<chunk.ref/WareHouse/

<chunk.ref/{ExploreOne WareHouse}/

declare
<chunk.ref/WareHouseOrder/

<chunk.ref/{ExploreBest WareHouse}/




</chunk>
]]>

</chapter>

