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:
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:
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.
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.
v_{1} rel v_{1}' v_{2} rel v_{2}'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