generalised bin packing example

From: Anthony Karageorgos <>
Date: Tue 22 May 2001 12:18:07 PM GMT
Message-ID: <008101c0e2b9$42f05e10$>
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),

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 Karageorgos

Room L14
Dept. of Computation
Manchester M60 1QD

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

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