Bin Packing Problems

In a Bin Packing Problem, we have a number of items (each with a given size), and a number of bins (each with a given capacity), and we try to find a way to pack the items into the available bins. Often we want to minimize the number of bins needed.

Using IC and Global Constraints

The ic_global library provides a bin packing constraint bin_packing/3 which can be used to solve constraint problems that involve bin packing.

For all the following examples, we assume we have loaded the following libraries:

:- lib(ic).                % the basic interval/finite domain solver
:- lib(ic_global).         % a collection of global constraints
:- lib(branch_and_bound).  % support for finding optimal solutions

We will use the following concepts:

BinSize: the size (maximum capacity) of each bin.
NItems: the number of items (and the length of the lists ItemSizes and ItemBins).
ItemSizes: a list of item sizes. Items are identified by their position in this list.
ItemBins: a list of bin numbers, indicating into which which bin each item gets packed.
NBins: the number of bins (and the length of the list BinLoads).
BinLoads: a list with one entry per bin, indicating how full the bin is.

The bin packing constraint takes the form bin_packing(ItemBins,ItemSizes,BinLoads), and it would succeed for instance in the following case:

?- bin_packing([1, 2, 1, 2], [3, 2, 7, 8], [10, 10]).
Yes (0.00s cpu)

Here, we have 4 items that get packed into two bins. The items with size 3 and 7 go into bin 1, and the items with size 2 and 8 into bin 2. Both bins end up with a load of 10.

Finding Valid Packings

To actually solve a given problem, we have to combine the constraint with a search routine. We will initially assume that the number of bins (NBins) is fixed:

binpack_solve(ItemSizes, BinSize, NBins, ItemBins, BinLoads) :-
    length(ItemSizes, NItems),
    length(ItemBins, NItems),
    length(BinLoads, NBins),
    ItemBins :: 1..NBins,
    BinLoads :: 0..BinSize,
    bin_packing(ItemBins, ItemSizes, BinLoads),

    search(ItemBins, 0, first_fail, indomain, complete, []).

This can be called as follows. We want to find out how 4 items with given sizes can be packed into 2 bins of capacity 10:

?- binpack_solve([3, 2, 7, 8], 10, 2, ItemBins, BinLoads).
ItemBins = [1, 2, 1, 2]
BinLoads = [10, 10]
Yes (0.00s cpu, solution 1, maybe more)

ItemBins = [2, 1, 2, 1]
BinLoads = [10, 10]
Yes (0.03s cpu, solution 2, maybe more)
No (0.04s cpu)

Given item sizes, bin capacity and number, we obtain all solutions for packing these items into the given bins. Note that we get two (symmetrical) solutions, because the constraint distinguishes the individual bins.

Minimizing the Number of Bins

Often, we want to find the smallest number of bins needed to pack a given set of items. However, the bin_packing/3 constraint works on a fixed number of bins. One method is to to set up the bin_packing/3 constraint with a worst case number of bins (e.g. the naive upper bound of one bin per item), but add an additional constraint (here called bins_used/2) that restricts the number of usable bins to a variable number (here BinsUsed). This number can then be minimized using the generic branch-and-bound primitives:

binpack_min(ItemSizes, BinSize, ItemBins, BinLoads, BinsUsed) :-
    length(ItemSizes, NItems),
    length(ItemBins, NItems),
    MaxBins = NItems,                % worst case: one bin per item
    length(BinLoads, MaxBins),
    ItemBins :: 1..MaxBins,
    BinLoads :: 0..BinSize,
    bin_packing(ItemBins, ItemSizes, BinLoads),
    bins_used(BinLoads, BinsUsed),  % use only BinUsed bins

    bb_min(
        search(ItemBins, 0, first_fail, indomain_min, complete, []),
        BinsUsed,                   % Minimize the number of bins used
        bb_options{strategy:restart,timeout:60}).

% Auxiliary: allow only the first Used bins to be nonzero
bins_used(BinLoads, Used) :-
    ( foreach(Load,BinLoads), fromto([],Bs0,[B|Bs0],Bs) do
        B #= (Load #> 0)
    ),
    ordered_sum(Bs, Used).

Here is a sample execution. It gives an optimal solution to the problem of packing the 4 given items into bins of capacity 10. Three bins are needed, as indicated by the 3 leading nonzero elements in BinLoads:

?- binpack_min([3, 4, 6, 8], 10, ItemBins, BinLoads, BinsUsed).
Found a solution with cost 3
Found no solution with cost 0.0 .. 2.0
ItemBins = [1, 1, 3, 2]
BinLoads = [7, 8, 6, 0]
BinsUsed = 3
Yes (0.01s cpu)

BinPacking

Bin Packing Problems

Using IC and Global Constraints

Finding Valid Packings

Minimizing the Number of Bins