Problem description

Packing of items into boxes or bins is a recurring task in distribution and production. Concerning the size and shape of items as well as the form and capacity of bins a large variety of different packing problems can be distinguished. Similar problems concern cutting of pieces into particular smaller ones so as to minimize the wastage of material and scheduling of identical parallel processors so as to minimize the total completion time. We consider a basic packing problem which is known as the one-dimensional bin packing problem (BPP-1, cf. Martello and Toth, 1990). It is to pack a given set of items having different sizes into a minimum number of equal-sized bins. Even though this problem seems to be rather simple it is NP-hard, i.e., no procedure is able to solve each problem instance in polynomial time. In order to solve more general (and more complex) realistic problems within reasonable computation time it is important to have on hand effective procedures for the basic problem.

Solution procedures

We propose an exact hybrid solution procedure for BPP-1 (called BISON) which combines the successful heuristic meta strategy tabu search and a branch and bound procedure. The tabu search procedure utilizes the relationship of BPP-1 to BPP-2 (minimize the size of the bins given their number) through the so-called dual strategy. The branch and bound procedure is based on a clever branching scheme called local lower bound method.
Computational results indicate that BISON is very effective and outperforms the well-known procedure MTP of Martello and Toth (1990).

Test data

We present benchmark data sets for BPP-1 which may be used to test and compare solution procedures. The first data set (720 instances) is constructed similar to that used by Martello and Toth (1990) for testing their procedure MTP. The second data set (480 instances) contains parameter settings not covered by the first set, while the third set contains 10 hard instances. You may find information on the data sets and download the data of all problem instances (defined through the number of items, the bin capacity, and the weights of all items (in decreasing order) by choosing the following links:

Data set 1

Data set 2

Data set 3

References:

• S. Martello and P. Toth, Knapsack problems. Wiley, Chichester (1990).
• A. Scholl, R. Klein, and C. Jürgens: BISON: a fast hybrid procedure for exactly solving the one-dimensional bin packing problem. Computers & Operations Research 24 (1997) 627-645.