# generalised bin packing example

From: Anthony Karageorgos <mcaihak2_at_co.umist.ac.uk>
Date: Tue 22 May 2001 12:18:07 PM GMT
Message-ID: <008101c0e2b9\$42f05e10\$d6d19284@futures.bt.co.uk>
```Dear all,

I have obtained ECLiPSe recently. What I need to do is solve a problem similar to the bin packing example described in the fd library documentation. There are some differences, however and the most significant one is the following:

In the bin packing example 5 types components (glass, plastic, steel, wood, copper)  need to be placed in bins of 3 types (red, blue, green)  such as various constraints hold. The example minimises the number of bins of each bin type required to store a given number of components of each component type.

The solution is based on a cont(Glass, Plastic, Steel, Wood, Copper)structure (for clarity I am attaching a part of the example below)

solve(Bins) :-
solve_bin(cont(1, 2, 1, 3, 2), Bins).

solve_bin(Demand, Bins) :-
Demand = cont(G, P, S, W, C),
Sum is G + P + S + W + C,
bins(Demand, Sum, [Sum, Sum, Sum, Sum, Sum, Sum], Bins),
label(Bins).

bins(cont(0, 0, 0, 0, 0), 0, _, []).
bins(cont(G0, P0, S0, W0, C0), Sum0, LastBin, [Bin|Bins]) :-
Bin = [_Col, G, P, S, W, C],
bin(Bin, Sum),
G2 #= G0 - G,
P2 #= P0 - P,
S2 #= S0 - S,
W2 #= W0 - W,
C2 #= C0 - C,
Sum2 #= Sum0 - Sum,
ordering(Bin, LastBin),
bins(cont(G2, P2, S2, W2, C2), Sum2, Bin, Bins).

In my case I do not know the number of component types in advance and therefore I cannot use a similar structure. For example, I would like to have a list of component types and some exclusion constraints described as facts and start from there.

How would you reccommend me to model such a problem in order to solve it using ECLiPSe?

Many thanks

Anthony

---------------------------------------
Anthony Karageorgos

Room L14
Dept. of Computation
UMIST
Manchester M60 1QD
UK

tel. +44-161-2003306
fax. +44-161-2003324

e-mail: mcaihak2@co.umist.ac.uk
```
Received on Tue May 22 13:24:03 2001

This archive was generated by hypermail 2.1.8 : Wed 16 Nov 2005 06:07:09 PM GMT GMT