20. Bin packing¶
This chapter studies the classic bin packing problem. Three models are presented: a first and naive model (presented in A naive model ) that suffers from poor propagation to be feasible. This is followed by a model ( Improving propagation ) that uses the special binpacking constraint to drastically improve constraint propagation. A final model improves the second model by a problem-specific branching ( Improving branching ) that also breaks many symmetries during search.
Important
This case study requires knowledge on programming branchers, see Programming branchers .
20.1. Problem¶
The bin packing problem consists of packing \(\mathtt{n}\) items of sizes \(\mathtt{size}_i\) (\(0\leq i<\mathtt{n}\)) into the smallest number of bins such that the capacity \(\mathtt{c}\) of each bin is not exceeded.
Figure 20.1 An example optimal bin packing¶
For example, the \(11\) items of sizes
require at least four bins of capacity \(10\) as shown in Figure 20.1 where the items are numbered starting from zero.
20.2. A naive model¶
Before turning our attention to a naive model for the bin packing problem, this section discusses instance data for the bin packing problem and how to compute lower and upper bounds for the number of required bins.
20.2.1. Instance data.¶
const int c = 100;
const int n = 50;
const int size[n] = {
99,98,95,95,95,94,94,91,88,87,86,85,76,74,73,71,68,60,55,54,51,
45,42,40,39,39,36,34,33,32,32,31,31,30,29,26,26,23,21,21,21,19,
18,18,16,15,5,5,4,1
};
Instance data. shows an example instance of a bin packing problem, where n defines the number of items, c defines the capacity of each bin, and the array size defines the size of each item. For simplicity, we assume that the item size are ordered in decreasing order.
The data corresponds to the instance N1C1W1_N taken from [45] . More information on other data instances can be found in More information .
20.2.2. Computing a lower bound.¶
int lower(void) {
int s=0;
for (int i=0; i<n; i++)
s += size[i];
return (s + c - 1) / c;
}
A simple lower bound \(L_1\) (following Martello and Toth [33] ) for the number of bins required for a bin packing problem just considers the size of all items and the bin capacity as follows:
The computation of the lower bound \(L_1\) is as to be expected and is shown in Computing a lower bound. . The ceiling operation is replaced by adding \(\mathtt{c}-1\) followed by truncating integer division with \(\mathtt{c}\).
Note that more accurate lower bounds are known, see More information for more information.
20.2.3. Computing an upper bound.¶
An obvious upper bound for the number of bins required is the number of items: each item is packed into a separate bin (provided that no item size exceeds the bin capacity c). A better upper bound can be computed by constructing a solution by packing items into bins following a first-fit strategy: pack all items into the first bin of sufficient free capacity.
int upper(void) {
int* free = new int[n];
for (int i=0; i<n; i++)
free[i] = c;
int u=0;
// [bin packing naive:pack items into free bins]
delete [] free;
return u+1;
}
Computing an upper bound for the number of bins shows the function upper() that returns an upper bound for the number of bins. It initializes an array free of n integers with the bin capacity c. The integer u refers to the index of the last used bin (that is, a bin into which an item has been packed). The function returns the number of used bins (that is, the index u plus one).
Each item is packed into a bin with sufficient free capacity where j refers to the next free bin:
for (int i=0; i<n; i++) {
int j=0;
// [bin packing naive:find free bin]
u = std::max(u,j);
}
The next free bin j is searched for as follows:
while (free[j] < size[i])
j++;
free[j] -= size[i];
The loop always terminates as there is one bin for each item.
Note that upper() has \(O(\mathtt{n}^2)\) complexity in the worst case but could be made more efficient by speeding up finding a fitting bin.
Figure 20.2 A non-optimal bin packing found during upper-bound computation¶
The solution constructed during computation of upper() is not necessarily optimal. As an example, consider the packing computed by upper() for the example from Problem shown in Figure 20.2 : it takes five rather than four bins because one of the items 4 and 5 should be packed together with item 3 rather than with one of the items 0, 1, and 2.
If both lower and upper bound coincide the solution constructed is of course optimal and we are done solving the bin packing problem. For reasons of simplicity, our model just forsakes this opportunity and re-computes an optimal solution by constraint programming.
20.2.4. Model proper.¶
...
// [bin packing naive:instance data]
// [bin packing naive:compute lower bound]
// [bin packing naive:compute upper bound]
class BinPacking : public IntMinimizeScript {
protected:
const int l;
const int u;
IntVarArray load;
IntVarArray bin;
IntVar bins;
public:
BinPacking(const Options& opt)
: IntMinimizeScript(opt),
l(lower()), u(upper()),
load(*this, u, 0, c),
bin(*this, n, 0, u-1), bins(*this, l, u) {
// [bin packing naive:excess bins]
int s=0;
for (int i=0; i<n; i++)
s += size[i];
IntArgs sizes(n, size);
// [bin packing naive:loads add up to item sizes]
// [bin packing naive:loads are equal to packed items]
// [bin packing naive:symmetry breaking]
// [bin packing naive:pack items that require a bin]
// [bin packing naive:branching]
}
virtual IntVar cost(void) const {
return bins;
}
...
};
...
Download: bin-packing-naive.cpp
Model proper. shows a script for the bin packing model. The script defines integers l and u that store the lower and upper bound as discussed above. A load variable \(\mathtt{load}_i\) (taking values from \(\{0,\ldots,\mathtt{c}\}\)) defines the total size of all items packed into bin \(i\). The script uses u load variables as the upper bound guarantees that u bins are sufficient to find an optimal solution. A bin variable \(\mathtt{bin}_i\) (taking values from \(\{0,\ldots,\mathtt{u}-1\}\) defines for each item \(i\) into which bin it is packed. The variable bins defines the number of used bins. A bin is used if at least one item is packed into it, otherwise it is an excess bin.
The integer s is initialized as the size of all items and sizes is initialized as an integer argument array of all sizes.
The cost() function as required by the class MinimizeScript (see Scripts ) returns the number of bins.
20.2.5. Excess bins.¶
If the script finds a solution that uses less than u bins, say k (the value of the bins variable), then \(\mathtt{u}-\mathtt{k}\) of the load variables corresponding to excess bins are zero. To remove many symmetrical solutions that only differ in which bins are excess bins, the script constrains the excess bins to be the bins \(\mathtt{k},\ldots,\mathtt{u}-1\):
for (int i=1; i<=u; i++)
rel(*this, (bins < i) == (load[i-1] == 0));
20.2.6. Constraining load and bin variables.¶
The sum of all load variables must be equal to the size of all items:
linear(*this, load, IRT_EQ, s);
The load variable for a bin must be constrained according to which items are packed into the bin. A standard formulation of this constraint uses Boolean variables \(\mathtt{x}_{i,j}\) which determine whether item \(i\) has been packed into bin \(j\). That is, for each item \(0\leq i<\mathtt{n}\) the following constraint must hold:
A more efficient propagator for the very same constraint is available as a channel constraint between an array of Boolean variables and a single integer variable, see Channel constraints . That is, for each item \(0\leq
i<\mathtt{n}\) the following constraint must hold:
Note that \(\langle
\mathtt{x}_{i,0},\mathtt{x}_{i,1},\ldots,
\mathtt{x}_{i,u-1}\rangle\) corresponds to x.col(\(i\)).
Furthermore, the size of all items packed into a bin must equal the corresponding load variable. Both constraints are expressed as follows, using a matrix x (see Matrix interface for arrays ) of Boolean variables _x:
BoolVarArgs _x(*this, n*u, 0, 1);
Matrix<BoolVarArgs> x(_x, n, u);
for (int i=0; i<n; i++)
channel(*this, x.col(i), bin[i]);
for (int j=0; j<u; j++)
linear(*this, sizes, x.row(j), IRT_EQ, load[j]);
20.2.7. Symmetry breaking.¶
Items of the same size are equivalent as far as the model is concerned. To break symmetries, the bins for items of the same size are ordered:
for (int i=1; i<n; i++)
if (size[i-1] == size[i])
rel(*this, bin[i-1] <= bin[i]);
The loop exploits that items are ordered according to size and hence items of the same size are adjacent.
20.2.8. Pack items that require a bin.¶
If the size \(s\) of an item exceeds \(\lceil\frac{\mathtt{c}}{2}\rceil\) (or, equivalently, \(2s>\mathtt{c}\)), the item cannot share a bin with any other item also exceeding half of the capacity. That is, items exceeding half of the capacity can be directly assigned to different bins:
for (int i=0; (i < n) && (i < u) && (size[i] * 2 > c); i++)
rel(*this, bin[i] == i);
The assignment of items to bins is compatible with the symmetry breaking constraints discussed previously.
20.2.9. Branching.¶
We choose a naive branching strategy that first branches on the number of required bins, followed by trying to assign items to bins.
branch(*this, bins, INT_VAL_MIN());
branch(*this, bin, INT_VAR_NONE(), INT_VAL_MIN());
Note that by choosing the bin variables with order INT_VAR_NONE() assigns the largest item to a bin first as items are sorted by decreasing size.
The script in Model proper. does not show that the script uses branch-and-bound search to find a best solution. Why depth-first search is not sufficient with parallel search is discussed in Do not optimize by branching alone .
20.2.10. Running the model.¶
When running the naive model (All measurements in this chapter have been made on a laptop with an Intel i5 M430 processor (2.27 GHz, two cores, hyper-threading), 4 GB of main memory, running Windows 7 x64, and using Gecode 3.4.3.), it becomes apparent that the model is indeed naive. Finding the best solution takes \(29.5\) seconds and \(2\,451\,018\) failures. Clearly, that leaves ample room for improvement in the following sections!
20.3. Improving propagation¶
This section improves (and simplifies) the naive model from the previous section by using a dedicated binpacking constraint.
...
class BinPacking : public IntMinimizeScript {
...
public:
BinPacking(const Options& opt)
...
IntArgs sizes(n, size);
binpacking(*this, load, bin, sizes);
...
}
...
};
...
Download: bin-packing-propagation.cpp
20.3.1. Model.¶
The improved model is shown in A script with improved propagation for solving a bin packing problem . Instead of using Boolean variables x, linear constraints, and channel constraints it uses the binpacking constraint (see also Bin-packing constraints ). The constraint enforces that the packing of items as defined by the bin variables corresponds to the load variables.
20.3.2. Running the model.¶
Finding a best solution using the model with improved propagation takes \(1.5\) seconds and \(64\,477\) failures. That is, this model runs almost \(20\) times faster than the naive model and reduces the number of failures by a factor of \(38\).
20.4. Improving branching¶
This section describes a problem specific branching to improve the model of the previous section even further.
20.4.1. Complete decreasing best fit branching.¶
The improved branching for bin packing is called complete decreasing best-fit (CDBF) and is due to Gent and Walsh [17] . The branching uses some additional improvements suggested by Shaw in [56] .
The branching tries to assign items to bins during search where the items are tried in order of decreasing size. The bin is selected according to a best fit strategy: try to put the item into a bin with sufficient but least free space. The space of the bin after packing an item is called the bin’s slack. If there is no bin with sufficient free space left, CDBF fails.
Suppose that CDBF selects item i and bin b. Then the following actions are taken during branching:
If there is a perfect fit (that is, the slack is zero), branching assigns item
ito binb. This corresponds to a branching with a single alternative.If all possible bins have the same slack, branching assigns item
ito binb. Again, this corresponds to a branching with a single alternative.Otherwise, CDBF tries two alternatives in the following order:
Assign item
ito binb.Not only prune bin
bfrom the potential bins for itemibut also prune all bins with the same slack asbfrom the potential bins for all items with the same size asi.
Note that the second alternative of CDBF performs symmetry breaking during search as it prunes also with respect to equivalent items and bins.
Also note that the symmetry breaking based on items of same size as discussed in A naive model cannot be used as it is incompatible with rule for a perfect fit (Thanks to Florian ??? for pointing this out.).
20.4.2. Model.¶
...
// [bin packing branching:CDBF]
class BinPacking : public IntMinimizeScript {
...
public:
BinPacking(const Options& opt)
...
branch(*this, bins, INT_VAL_MIN());
cdbf(*this, load, bin, sizes);
}
...
};
...
Download: bin-packing-branching.cpp
The only change to the model compared to Improving propagation is that it uses the branching cdbf for assigning items to bins during search.
20.4.3. Brancher creation.¶
class CDBF : public Brancher {
protected:
ViewArray<Int::IntView> load;
ViewArray<Int::IntView> bin;
IntSharedArray size;
mutable int item;
// [bin packing branching:CDBF choice]
public:
CDBF(Home home, ViewArray<Int::IntView>& l,
ViewArray<Int::IntView>& b,
IntSharedArray& s)
: Brancher(home), load(l), bin(b), size(s), item(0) {
home.notice(*this,AP_DISPOSE);
}
static void post(Home home, ViewArray<Int::IntView>& l,
ViewArray<Int::IntView>& b,
IntSharedArray& s) {
(void) new (home) CDBF(home, l, b, s);
}
// [bin packing branching:status function]
// [bin packing branching:choice function]
// [bin packing branching:commit function]
...
virtual size_t dispose(Space& home) {
home.ignore(*this,AP_DISPOSE);
size.~IntSharedArray();
(void) Brancher::dispose(home);
return sizeof(*this);
}
};
void cdbf(Home home, const IntVarArgs& l, const IntVarArgs& b,
const IntArgs& s) {
if (b.size() != s.size())
throw Int::ArgumentSizeMismatch("cdbf");
ViewArray<Int::IntView> load(home, l);
ViewArray<Int::IntView> bin(home, b);
IntSharedArray size(s);
CDBF::post(home, load, bin, size);
}
The cdbf branching takes load variables (for computing the free space of a bin), bin variables (to pack items into bins), and the item sizes (to compute how much space an item requires) as input and posts the CDBF brancher as shown in Brancher creation. .
The branching post function cdbf() creates view arrays for the respective variables, creates a shared integer array of type IntSharedArray (see Shared integer arrays ) and posts a CDBF brancher. The advantage of using a shared array is that the sizes are stored only once in memory and branchers in different spaces have shared access to the same memory area (see also Shared objects and handles ).
The brancher CDBF stores the load variables, bin variables, and item sizes together with an integer item. The integer item is used to find the next unassigned item. It is declared mutable so that the const status() function (see below) can modify it. The brancher exploits that the items are sorted by decreasing size: by initializing item to zero the brancher is trying to pack the largest item first.
By default, the dispose() member function of a brancher is not called when the brancher’s home space is deleted. However, the dispose() function of the CDBF brancher must call the destructor of the shared integer array size. Hence, the constructor of CDBF calls the notice() function of the home space so that the brancher’s dispose() function is called when home is deleted (see also Calling dispose() during space deletion. ). Likewise, the dispose() function calls the ignore() function before the brancher is disposed.
20.4.4. Status computation.¶
The status() function tries to find a yet unassigned view for branching in the view array bin. It starts inspecting the views at position item and skips all already assigned views. If there is a not yet assigned view left, item is updated to that unassigned view and true is returned (that is, more branching is needed). Otherwise, the brancher returns false as no more branching is needed:
virtual bool status(const Space&) const {
for (int i = item; i < bin.size(); i++)
if (!bin[i].assigned()) {
item = i; return true;
}
return false;
}
As the items are sorted by decreasing size, the integer item refers to the largest not-yet packed item.
20.4.5. Choice computation: initialization.¶
The choice() function implements the actual heuristic. The function uses n for the number of items, m for the number of bins, and initializes a region for managing temporary memory (see Region. ) as follows:
virtual Gecode::Choice* choice(Space& home) {
int n = bin.size(), m = load.size();
Region region;
// [bin packing branching:initialize free space in bins]
// [bin packing branching:initialize bins with same slack]
// [bin packing branching:find best fit]
// [bin packing branching:create choice]
}
The choice() function can rely on the fact that it is immediately executed after the status() function has been executed. That entails that item refers to the largest not-yet packed item.
The function computes in free the free space of each bin. From the maximal load the size of items that have already been packed (that is, the item’s bin variable is already assigned) is subtracted:
int* free = region.alloc<int>(m);
for (int j=0; j<m; j++)
free[j] = load[j].max();
for (int i=0; i<n; i++)
if (bin[i].assigned())
free[bin[i].val()] -= size[i];
The choice() function uses the integer slack to track the slack of the so-far best fit (initialized with INT_MAX such that any fit will be better). The integer n_possible counts the number of possible bins for the item whereas n_same counts the number of best fits. The array same stores all bins with the same so-far smallest slack.
int slack = INT_MAX;
unsigned int n_possible = 0;
unsigned int n_same = 0;
int* same = region.alloc<int>(m+1);
same[n_same++] = -1;
The array same is initialized to contain the bin -1: if no bin has sufficient space for the current item this will guarantee that the commit() function (see below) leads to failure.
20.4.6. Choice computation: create choice.¶
In order to find all best fits, all bins are examined. If the current item fits into a bin, the number of possible bins n_possible is incremented and all best fits are remembered in the array same as follows:
for (Int::ViewValues<Int::IntView> j(bin[item]); j(); ++j)
if (size[item] <= free[j.val()]) {
n_possible++;
if (free[j.val()] - size[item] < slack) {
slack = free[j.val()] - size[item];
n_same = 0;
same[n_same++] = j.val();
} else if (free[j.val()] - size[item] == slack) {
same[n_same++] = j.val();
}
}
Note that finding a better fit updates slack and resets the bins stored in same.
Now, the choice() function determines whether a special case needs to be dealt with:
Is the best fit a perfect fit: that is,
slackis zero?Are all fits a best fit: that is,
n_sameis equal ton_possible?Is there no fitting bin: that is,
n_possibleis zero?
In these cases a choice with a single alternative and otherwise a choice with two alternatives is created:
if ((slack == 0) ||
(n_same == n_possible) ||
(n_possible == 0))
return new Choice(*this, 1, item, same, 1);
else
return new Choice(*this, 2, item, same, n_same);
class Choice : public Gecode::Choice {
public:
int item;
int* same;
int n_same;
Choice(const Brancher& b, unsigned int a, int i, int* s, int n_s)
: Gecode::Choice(b,a), item(i),
same(heap.alloc<int>(n_s)), n_same(n_s) {
for (int k=0; k<n_same; k++)
same[k] = s[k];
}
virtual ~Choice(void) {
heap.free<int>(same,n_same);
}
virtual void archive(Archive& e) const {
Gecode::Choice::archive(e);
e << alternatives() << item << n_same;
for (int i=n_same; i--;) e << same[i];
}
};
The definition of the choice class is shown in CDBF choice . The choice stores the current item and in the array same all bins with the same slack. The choice does not need to store any information regarding items of same size as this information is available from the brancher.
20.4.7. Commit function.¶
The commit() function takes a choice of type CDBF::Choice and the alternative a (either 0 or 1) as input:
virtual ExecStatus commit(Space& home, const Gecode::Choice& _c,
unsigned int a) {
const Choice& c = static_cast<const Choice&>(_c);
if (a == 0) {
// [bin packing branching:commit to first alternative]
} else {
// [bin packing branching:commit to second alternative]
}
return ES_OK;
}
Committing to the first alternative tries to pack item into the first bin stored in same as follows:
GECODE_ME_CHECK(bin[c.item].eq(home, c.same[0]));
Committing to the second alternative removes all n_same bins stored in same from all items that have the same size as item as follows:
int i = c.item;
do {
Iter::Values::Array same(c.same, c.n_same);
GECODE_ME_CHECK(bin[i++].minus_v(home, same));
} while ((i < bin.size()) &&
(size[i] == size[c.item]));
The iterator Iter::Values::Array iterates over all values stored in an array (they must be in sorted order) and the operation minus_v() prunes all values as defined by an iterator from a view, see Iterator-based modification operations .
20.4.8. Running the model.¶
Finding a best solution using the model with improved propagation and improved branching takes \(84\) milliseconds and \(3\,098\) failures. That is, this model runs \(352\) times faster than the naive model and reduces the number of failures by a factor of \(791\).
20.5. More information¶
Bin packing featuring all models presented in this chapter is also available as a Gecode example, see bin-packing . The example also makes use of a more accurate lower bound known as \(L_2\) [33] .