Bin Packing

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:

There are 5 types of items:
glass, plastic, steel, wood, copper
There are three types of bins:
red, blue, green
The capacity constraints imposed on the bins are:
- red has capacity 3
- blue has capacity 1
- green has capacity 4
The containment constraints imposed on the bins are:
- red can contain glass, wood, copper
- blue can contain glass, steel, copper
- green can contain plastic, wood, copper
The requirement constraints imposed on component types (for all bin types) are:
wood requires plastic
Certain component types cannot coexist:
- glass and copper exclude each other
- copper and plastic exclude each other
The following bin types have the following capacity constraints for certain components:
- red contains at most 1 wood item
- blue implicitly contains at most 1 wood item
- green contains at most 2 wood items
Given the initial supply stated below, what is the minimum total number of bins required to contain the components?
- 1 glass item
- 2 plastic items
- 1 steel item
- 3 wood items
- 2 copper items

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 ECLⁱPS^e 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:

The number of items of each kind in the bin is non-negative.
The sum of all the items does not exceed the capacity of the bin.
and the bin is non-empty (an empty bin serves no purpose)

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 ECLⁱPS^e can be found in section 12.