The problem of bin packing raises of the Operations research and the combinative Optimization. It is a question of finding the arrangement most economic possible for a whole of articles in boxes. The traditional problem is defined in a dimension, but there exist many alternatives into two or three dimensions.

Practical applications

The problem of bin packing can be applied to a great number of industrial sectors or data processing.

For the traditional version in a dimension:

• arrangement of files on a computer support;
• cutting of cables;
• filling of trucks or containers with like only constraint the weight or the volume of the articles.

For the version in two dimensions:

• cutting of raw material
• placement of boxes on a pallet (without superposition of boxes)
• placement in a warehouse (without superposition of boxes)

For the version in three dimension:

• arrangement of objects in boxes, trucks, etc… (with superposition of boxes)

Formulation of the problem

In the traditional problem, the data are:

• an infinite number of boxes of size $C$
• a list $1,2,\; \backslash \; ldots,\; n$ of articles $i$ of size $c\_i$.

One seeks to find the arrangement valid for all these articles who minimizes the number of boxes used. So that an arrangement is valid, the sum of the sizes of the articles assigned to a box must be lower or equal to $C$.

To describe a solution, one can use a binary coding to indicate in which box $j$ each $i$ object is arranged.

• the variable $x\_\; \{ij\}$ will be worth $1$ if the article $i$ is arranged in the box $j$, and $0$ if not.
• the binary variable $y\_j$ is equal to $1$ if the box $j$ is used, $0$ if not.

One thus seeks to minimize the number of boxes used

$min\; \backslash sum\_\{j=1\}^n\; y\_j$

Under the following constraints:

$\backslash \; sum\_\; \{i=1\}\; ^\; \{N\}\; c\_i\; x\_\; \{ij\}\; \backslash \; Leq\; C\; y\_j,\; j=1,\; \backslash \; ldots,\; N$

$\backslash \; sum\_\; \{j=1\}\; ^\; \{N\}\; x\_\; \{ij\}\; =\; 1,\; i=1,\; \backslash \; ldots,\; N$

$x\_\; \{I,\; J\}\; \backslash \; in\; \backslash \; \{0,1\; \backslash \},\; i=1,\; \backslash \; ldots,\; N,\; j=1,\; \backslash \; ldots,\; n$

$y\_j\; \backslash \; in\; \backslash \; \{0,1\; \backslash \},\; j=1,\; \backslash \; ldots,\; N$

The first inequality means that one cannot exceed the size of a box for an arrangement. It should be noted that the right part of the inequality obliges $y\_j$ to take the value $1$ as soon as an article is arranged in the box $j$. The second inequality forces all the objects to be arranged in a box and only one. Any solution for which the preceding family of equations is checked is known as realizable .

Modeling described above was proposed by Leonid Kantorovich in 1960. There exist other linear formulations for this problem, in the form of a maximum problem of flood in a graph, or using a Décomposition of Dantzig and Wolfe.

Np-complétude

See also: Theory of complexity

This problem belongs to the class of the Np-difficult problems , one cannot solve it using a algorithm of polynomial complexity. The proof of this result is done by reduction starting from the problem of bipartition.

Methods of resolution

The problem of bin packing was largely studied in the community of operations research. There exist heuristic very effective to solve it, and a very effective modeling using the linear Programming.

Discovery method

See also: Heuristic

To solve the problem of bin packing, simple algorithms are often used as first-made decreasing (FFD) or best-made decreasing (BFD). The two methods function according to a similar principle: one sorts the list of articles by decreasing order of size, then one arranges each article in the order. In first-made , one arranges the article running in the first box which can contain it. In best-made , one arranges the article in the box best filled which can contain it. These algorithms are not optimal, but they make it possible to obtain very good performances in practice.

The algorithms Best the FIT Decreasing and First the FIT Decreasing never use again 11/9  OPT  +  1 boxes (where OPT is the optimal number of boxes in an optimal solution). The procedure of sorting is the most expensive part of the algorithm, but without it, the quality of the method is much less good. One obtains in this case of the solutions using at worst the 17/10  OPT  +  2 boxes.

A more effective version of FFD uses with the more 71/60  OPT  +  1 boxes.

Exact methods

One uses today primarily the linear Programming of integers to solve this problem. When the treated authority is of low size, the formulation of Kantorovich can be used. When the number of articles is large, one rather uses a resolution by Génération of columns using the model of Gilmore and Gomory, or the models resting on the resolution of a problem of maximum flood. The great quality of the methods obtained is due to excellent the linear relieving of the model .

Extensions, generalizations

The problem of bin packing has strong connections with the Problème of the backpack (knapsack) . These two problems are the most known representatives of what is called in the community of operations research the problems of cutting and conditioning (cutting and packing).

There exist many extensions for the basic problem of bin packing. One can consider these articles having two or three dimensions, prohibit certain articles from being arranged in the same box, or authorize the use of boxes of different sizes. The objects can take different forms: rectangles (paved), circles (spheres). When the forms are not convex, one will speak rather about problem of nesting .

The version of the problem where one does not know the list of objects by advance was lengthily studied. One speaks about version on-line of the problem.

When of the same articles size appear many times in the problem, one will speak rather about problem of cutting-stock .

See too

• Problem of the backpack
• List of Np-complete problems