Subsections

## Example: Bin Packing

This example features a nontrivial model involving reified constraints and nontrivial defined constraints.

### Problem Specification

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.

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.

The following constraints must hold for the contents of bins:

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

### Viewpoint and Constraints

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.

We will use a model that has both variables for bins and for components. The model has a variable mcap saying how many bins are used to pack the order. For every i 1 # mcap we have 6 variables:

• btypei denoting the type of the i-th bin.
• glassi denoting the number of glass components to be packed into the i-th bin.
• plasticidenoting the number of plastic components to be packed into the i-th bin.
• steeli denoting the number of steel components to be packed into the i-th bin.
• woodi denoting the number of wood components to be packed into the i-th bin.
• copperi denoting the number of copper components to be packed into the i-th bin.
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.

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.

### Branching Strategy

We branch on the type and capacity variables with the standard first - fail strategy. Because we want to get a packlist with a minimal number of bins used, you should first branch over the variable mcap and try smaller values first. Here, this is not possible because the vaue is used to create the lenght of the packing list and so has to be an integer value. To get this value of mcap you would need to reflect it's value during search. This is not possible!

We solve this problem with a test function, that uses the structure Search and in a loop that tries smaller values for mcap first and stops when the first solution is found.

### Script

The first defined constraint impl is used to post the following constraint:
v1   rel   v1' v2   rel   v2'
The function makebin creates a consistently packed bin with type btype and its components. It implements all the capacity, containment, requirement, and exclusion constraints of the problem specification.

The function makepacklist imposes constraints saying that packlist is a consistent packing list ordered as specified in the description of the model.

Match imposes constraints saying that the packing list packlist matches the order order.

type bin = {btype : FD.intvar, copper : FD.intvar,
glass : FD.intvar,plastic : FD.intvar,
steel : FD.intvar, wood : FD.intvar}

type packlist =
{btype : FD.intvar, copper : FD.intvar,
glass : FD.intvar,plastic : FD.intvar,
steel : FD.intvar, wood : FD.intvar} list

type order =
{copper : int, glass : int, plastic : int,
steel : int, wood : int}

(* posts an implication of two relations *)
fun impl(space,v1,rel1,v1',v2,rel2,v2')=
let
val tmp1 = FD.boolvar space
val tmp2 = FD.boolvar space
val tmp3 = FD.boolvar space
val tru = FD.intvar2boolvar(space,
FD.range(space,(1,1)))
in
FD.Reified.rel(space,v1,rel1,v1',tmp1);
FD.Reified.rel(space,v2,rel2,v2',tmp2);
FD.impl(space,tmp1,tmp2,tru)
end

fun makebin(space) =
let
val cap = FD.range(space,(1,4))
(* b is the type of a bin *)
val b = FD.range(space,(0,2))
val components as #[g,p,s,w,c] =
FD.rangeVec(space,5,(0,4))
val bin = {btype = b,glass = g,plastic = p,
steel = s,wood = w,copper = c}
val tru = FD.intvar2boolvar
(space,FD.range(space,(1,1)))
(* posts an implication of two relations with
constants*)
fun implI(space,v1,rel1,const1,v2,rel2,const2)=
let
val tmp1 = FD.boolvar space
val tmp2 = FD.boolvar space
in
FD.Reified.relI(space,v1,rel1,const1,tmp1);
FD.Reified.relI(space,v2,rel2,const2,tmp2);
FD.impl(space,tmp1,tmp2,tru)
end
fun implist(a as (a1,r1,a2),
rellist as((b1,r2,b2)::bs))=
List.app(fn(x,y,z)=>
implI(space,a1,r1,a2,x,y,z))rellist
in
post(space,SUMV(components) = FD(cap),FD.DOM);
implI(space,w,FD.GR,0,p,FD.GR,0);
implI(space,g,FD.GR,0,c,FD.EQ,0);
implI(space,c,FD.GR,0,p,FD.EQ,0);
implist((b,FD.EQ,1),[(cap,FD.EQ,3),(p,FD.EQ,0),
(s,FD.EQ,0),(w,FD.LQ,1)]);
implist((b,FD.EQ,0),[(cap,FD.EQ,1),(p,FD.EQ,0),
(w,FD.EQ,0)]);
implist((b,FD.EQ,2),[(cap,FD.EQ,4),(g,FD.EQ,0),(s,FD.EQ,0),
(w,FD.LQ,2)]);
bin
end

fun makepacklist list space =
let
val packlist = List.map(fn x => makebin(space))list
fun order(space,(x:bin)::nil) = ()
| order(space,x::y::xs)=
(FD.rel(space,((#btype)x),FD.LQ,((#btype)y));
impl(space,((#btype)x),FD.EQ,((#btype)y),
((#glass)x),FD.GQ,((#glass)y)))
in
order(space,packlist);
packlist
end

val order = {glass=2,plastic = 4,steel =3,
wood =6,copper =4}

fun match (packlist:packlist)(order:order)space =
let
val order' = #[#glass(order),#plastic(order),
#steel(order),#wood(order),#copper(order)]
val a = List.map(fn x => ((#glass)x))packlist
val b = List.map(fn x => (#plastic)x)packlist
val c = List.map(fn x => (#steel)x)packlist
val d = List.map(fn x => (#wood)x)packlist
val e = List.map(fn x => (#copper)x)packlist
in
Vector.appi(fn(i,x)=> post(space,SUMV(Vector.fromList x)
=  (Vector.sub(order',i)),FD.DOM))
(#[a,b,c,d,e])
end

fun binpacking order mcap space =
let
val nbcomp = #glass(order) + #plastic(order)+
#steel(order) + #wood(order) +
#copper(order)
val list = List.tabulate(mcap,fn x => x)
val packlist = makepacklist list space
val branchlist = List.map(fn x =>
[(#btype)x,(#copper)x,(#steel)x,
(#glass)x,(#plastic)x,(#wood)x])
packlist
val branchvec = Vector.fromList(List.concat(branchlist))
in
match packlist order space;
FD.branch(space,branchvec,FD.B_SIZE_MIN,FD.B_MIN);
packlist
end

(* insert a value > 0 for x and findsolution finds the
minimal number of bins

fun findsolution x =
let
val res =  (Search.searchOne(binpacking order x))
handle Space.InvalidSpace => NONE
in
case res of NONE => findsolution (x+1)
| SOME(s,r) =>
List.map(fn y =>
List.map(fn z => FD.Reflect.value(s,z))
([(#btype)y,(#copper)y,(#steel)y,
(#glass)y,(#plastic)y,(#wood)y]))r
end
*)
`

The result of findsolution (1 ) is a list of lenght 8, where every element is a bin with it's type and components:

[[0, 0, 1, 0, 0, 0],[0, 0, 1, 0, 0, 0],[1, 0, 0, 2, 0, 0],
[2, 4, 0, 0, 0, 0],[2, 0, 0, 0, 1, 2],[2, 0, 0, 0, 1, 2],
[2, 0, 0, 0, 2, 2],[0, 0, 1, 0, 0, 0]]

Andreas Rossberg 2006-08-28