Subsections

## Example: Locating Warehouses

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

### Problem Specification

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.

We assume the fixed costs of building a warehouse to be 50. We furthermore assume 5 warehouses W1 through W5 and 10 stores Store 1 through Store 10. The capacities of the warehouses are:

 W1 W2 W3 W4 W5 capacity 1 4 2 1 3

The costs to supply a store by a warehouse are:

 W1 W2 W3 W4 W5 Store 1 36 42 22 44 52 Store 2 49 47 134 135 121 Store 3 121 158 117 156 115 Store 4 8 91 120 113 101 Store 5 77 156 98 135 11 Store 6 71 39 50 110 98 Store 7 6 12 120 98 93 Store 8 20 120 25 72 156 Store 9 151 60 104 139 77 Store 10 79 107 91 117 154

### Viewpoint and Constraints

We assume that the costs are given in the matrix CostMatrix defined above. For the model of this problem we introduce the following variables.
• Openi, 1 i 5, with domain 0#1 such that Openi = 1 if warehouse Wi does supply at least one store.
• Supplieri, 1 i 10, with domain 1#5 such that Supplieri = j if store is supplied by warehouse Wj.
• Costi, 1 i 10, such that the domain of Costi is defined by the row CostMatrixi. The variable Costi denotes the costs of supplying store by warehouse WSupplieri, i. e., Costi = CostMatrixi,Supplieri.
We have the additional constraint that the capacity of the warehouses must not be exceeded. To this aim we introduce auxiliary variables Suppliesi, j with the domain 0#1 as follows:
i {1,..., 5}j {1,..., 10}: (Suppliesi, j = 1) (Supplierj = i)

The capacity constraints can then be stated with

i {1,..., 5} :  Capi Suppliesi, j
where Capi is defined defined above10.3.1.

### Branching Strategy

There are several possibilities to define a branching strategy for this problem.

We choose to determine the variables Costi by branching. 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 Costi 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 branching strategy will try the minimal value in the domain of Costi first. In Operations Research this strategy is known as the principle of least regret.

### Script

val capacity = #[3,1,4,1,4];

val costmatrix =
#[#[36,42,22,44,52],#[49,47,134,135,121],
#[121,158,117,156,115],#[8,91,120,113,101],
#[77,156,98,135,11],#[71,39,50,110,98],
#[6,12,120,98,93],#[20,120,25,72,156],
#[151,60,104,139,77],#[79,107,91,117,154]];

val maxValue = (valOf (Int.maxInt))div 2

fun warehouse cap costm space =
let
val isopen as #[o1,o2,o3,o4,o5] =
FD.boolvarVec(space,5)
val supplier as #[s0,s1,s2,s3,s4,s5,s6,s7,s8,s9] =
FD.rangeVec(space,10,(0,4))
val cost as #[c0,c1,c2,c3,c4,c5,c6,c7,c8,c9] =
FD.rangeVec(space,10,(1,1000))
val suppliesij = Vector.tabulate(5,fn x =>
FD.boolvarVec(space,10))
val sumcost = FD.range(space,(1,10000))
val nbopen = FD.range(space,(0,5))
val totalcost = FD.range(space,(1,11000))
fun order(curr,last)=
post (curr, FD(totalcost)<
(FD.Reflect.value(last,totalcost)),FD.BND)

in
(* posts sum of isopen[i] = nbopen *)
post(space,SUMV(Vector.map(fn x =>
FD.boolvar2intvar x)isopen) = FD(nbopen),FD.DOM);
(* posts sum of cost[i]= sumcost *)
post(space,SUMV(cost) = FD(sumcost),FD.DOM);
post(space,FD(sumcost)+ FD(nbopen) * 50
= FD(totalcost),FD.DOM);
(* ensures that for i={1,..,5}and j={1,..,10}:
supplies_{i,j} = 1 <-> supplier[j]=i *)
let
val tmp = Vector.concat(Vector.toList
(Vector.tabulate(5,fn x =>
Vector.tabulate(10,fn y =>(x,y)))))
in
Vector.app(fn(i,j) =>
FD.Reified.relI(space,
Vector.sub(supplier,j),FD.EQ,i,
Vector.sub(Vector.sub(suppliesij,i),j)))
tmp
end;
(* ensures that for i ={1,..,5}and j={1,..,10}:
capacity[i] >= sum supplies_{i,j} *)
Vector.app(fn(x) =>
post(space,SUMV(Vector.map(fn y =>
FD.boolvar2intvar y)(Vector.sub(suppliesij,x)))
<= (Vector.sub(cap,x)),FD.DOM))
(#[0,1,2,3,4]);
(* ensures that cost[i] = costmatrix_{i,(supplier[i])} *)
Vector.appi(fn(i,x) => FD.elementI( space,x,
Vector.sub(supplier,i),Vector.sub(cost,i)))
(costm);
(* ensures that open[i]= 1 <->
W_i does support at least one store *)
Vector.appi(fn(i,x) =>
let
val tmp = Vector.map(fn y => FD.boolvar2intvar y)x
val tmp2 =  FD.range(space,(0,5))
in
post(space,SUMV(tmp) = FD(tmp2),FD.DOM);
FD.Reified.relI(space,tmp2,FD.GR,0, Vector.sub(isopen,i))
end)
(suppliesij);
FD.branch(space,cost,FD.B_REGRET_MIN_MAX,FD.B_MIN);
({cost,totalcost,supplier,suppliesij,isopen,nbopen},order)
end
`

Andreas Rossberg 2006-08-28