alice
constraint
tutorial.
Next: Branch and Bound Up: Reified Constraints Previous: Example: Self-referential Aptitude Test Contents
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.
v1 rel v1'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.v2 rel v2'
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]]