Previous Up Next

8.8  Bin Packing

This section presents a worked example using finite domains to solve a bin-packing problem.

8.8.1  Problem Definition

In this type of problem the goal is to pack a certain amount of different items into the minimal number of bins under specific constraints. Let us solve an example given by Andre Vellino in the Usenet group comp.lang.prolog, June 93:

8.8.2  Problem Model - Using Structures

In modelling this problem we need to refer to an array of quantities of glass items, plastic items, steel items, wood items and copper items. We therefore introduce:

A structure to hold this array:

:- local struct(contents(glass, plastic, steel, wood, copper)).

A structure that defines the colour for each of the bin types:

:- local struct(colour(red, blue, green)).

By defining the bin colours as fields of a structure there is an implicit integer value associated with each colour. This allows the readability of the code to be preserved by writing, for example, red of colour rather than explicitly writing the colour’s integer value ‘1’.

And a structure that represents the bin itself, with its colour, capacity and contents:

:- local struct(bin(colour, capacity, contents:contents)).
The contents attribute of bin is itself a contents structure. The contents field declaration within the bin structure using ’:’ allows field names of the contents structure to be used as if they were field names of the bin structure. More information on accessing nested structures and structures with inherited fields can be found in section 4.1 and in the Structure Notation section of the ECLiPSe User Manual.

The predicate solve_bin/2 is the general predicate that takes an amount of components packed into a contents structure and returns the solution.

?- Demand = contents{glass:1, plastic:2, steel:1, wood:3, copper:2},
   solve_bin(Demand, Bins).

8.8.3   Handling an Unknown Number of Bins

solve_bin/2 calls bin_setup/2 to generate a list Bins. It adds redundant constraints to remove symmetries (two solutions are considered symmetrical if they are the same, but with the bins in a different order). Finally it labels all decision variables in the problem.

solve_bin(Demand, Bins) :-
    bin_setup(Demand, Bins),
    remove_symmetry(Bins),
    bin_label(Bins).

The usual pattern for solving finite domain problems is to state constraints on a set of variables, and then label them. However, because the number of bins needed is not known initially, it is awkward to model the problem with a fixed set of variables.

One possibility is to take a fixed, large enough, number of bins and to try to find a minimum number of non-empty bins. However, for efficiency, we choose to solve a sequence of problems, each one with a - larger - fixed number of bins, until a solution is found.

The predicate bin_setup/2, to generate a list of bins with appropriate constraints, works as follows. First it tries to match the (remaining) demand with zero, and use no (further) bins. If this fails, a new bin is added to the bin list; appropriate constraints are imposed on all the new bin’s variables; its contents are subtracted from the demand; and the bin_setup/2 predicate calls itself recursively:

bin_setup(Demand,[]) :- 
        all_zeroes(Demand).
bin_setup(Demand, [Bin | Bins]) :-
        constrain_bin(Bin),
        reduce_demand(Demand, Bin, RemainingDemand),
        bin_setup(RemainingDemand, Bins).

all_zeroes( 
           contents{glass:0, plastic:0, wood:0, steel:0, copper:0}
          ).

reduce_demand( 
              contents{glass:G, plastic:P, wood:W, steel:S, copper:C},
              bin{glass:BG, plastic:BP, wood:BW, steel:BS, copper:BC},
              contents{glass:RG, plastic:RP, wood:RW, steel:RS, copper:RC} 
             ) :-
       RG #= G - BG,
       RP #= P - BP,
       RW #= W - BW,
       RS #= S - BS,
       RC #= C - BC.

8.8.4  Constraints on a Single Bin

The constraints imposed on a single bin correspond exactly to the problem statement:

constrain_bin(bin{colour:Col, capacity:Cap, contents:C}) :-
        colour_capacity_constraint(Col, Cap),
        capacity_constraint(Cap, C),
        contents_constraints(C),
        colour_constraints(Col, C).
colour_capacity_constraint

The colour capacity constraint relates the colour of the bin to its capacity, we implement this using the relates/4 predicate (defined in section 8.6.3):

colour_capacity_constraint(Col, Cap) :-
    relates(Col, [red of colour, blue of colour, green of colour],
            Cap, [3, 1, 4]).
capacity_constraint

The capacity constraint states the following:

capacity_constraint(Cap, contents{glass:G,
                                   plastic:P,
                                   steel:S, 
                                   wood:W,
                                   copper:C}) :-
        G #>= 0, P #>= 0, S #>= 0, W #>= 0, C #>= 0,
        NumItems #= G + P + W + S + C,
        Cap #>= NumItems,
        NumItems #> 0.
contents_constraints

The contents constraints directly enforce the restrictions on items in the bin: wood requires paper, glass and copper exclude each other, and copper and plastic exclude each other:

contents_constraints(contents{glass:G, plastic:P, wood:W, copper:C}) :-
        requires(W, P),
        exclusive(G, C),
        exclusive(C, P).

These constraints are expressed as logical combinations of constraints on the number of items. ‘requires’ is expressed using implication, =>. ‘Wood requires paper’ is expressed in logic as ‘If the number of wood items is greater than zero, then the number of paper items is also greater than zero’:

requires(W,P) :-
        W #> 0 => P #> 0.

Exclusion is expressed using disjunction, or. ‘X and Y are exclusive’ is expressed as ‘Either the number of items of kind X is zero, or the number of items of kind Y is zero’:

exclusive(X,Y) :-
        X #= 0 or Y #= 0.
colour_constraints

The colour constraint limits the number of wooden items in bins of different colours. Like the capacity constraint, the relation between the colour and capacity, WCap, is expressed using the relates/4 predicate. The number of wooden items is then constrained not to exceed the capacity:

colour_constraints(Col, contents{wood:W}) :-
    relates(Col, [red of colour, blue of colour, green of colour],
            WCap, [1, 1, 2]),
    W #=< WCap.

This model artificially introduces a capacity of blue bins for wood items (set simply at its maximum capacity for all items).

8.8.5  Symmetry Constraints

To make sure two solutions (a solution is a list of bins) are not just different permutations of the same bins, we impose an order on the list of bins:

remove_symmetry(Bins) :-
        ( fromto(Bins, [B1, B2 | Rest], [B2 | Rest], [_Last])
        do
            lex_ord(B1, B2)
        ).

We order two bins by imposing lexicographic order onto lists computed from their colour and contents, (recall that in defining the bin colours as fields of a structure we have encoded them as integers, which allows them to be ordered):

lex_ord(bin{colour:Col1, contents:Conts1},
        bin{colour:Col2, contents:Conts2}) :-
        % Use ‘=..’ to extract the contents of the bin as a list
        Conts1 =.. [_ | Vars1],
        Conts2 =.. [_ | Vars2],
        lexico_le([Col1 | Vars1], [Col2 | Vars2]).

The lexicographic order is imposed using ic_global’s lexico_le/2 constraint.

8.8.6  Search

The search is done by first choosing a colour for each bin, and then labelling the remaining variables.

bin_label(Bins) :-
        ( foreach(bin{colour:C} Bins) do indomain(C) ),
        term_variables(Bins, Vars),
        search(Vars, 0, first_fail, indomain, complete, []).

The remaining variables are labelled by employing the first fail heuristic (using the search/6 predicate of the ic library).

Additional information on search algorithms, heuristics and their use in ECLiPSe can be found in section 12.

Previous Up Next