Research  > Bin Packing


Bin Packing

The one dimensional bin packing problem is defined follows. Given a set of items I={1,…,n} each having an associated size or weight wi and a set of bins with identical capacities c. The problem is to pack all the items into as few bins as possible, without exceeding the bin’s capacity. The bin packing problem is a well-known NP-Hard combinatorial optimisation problem (Martello and Toth, 1990a) and there has no known polynomial algorithm that can solve every problem instance to optimality. However, it is not difficult to get a lower bound of the problem. This problem can also be extended to two-dimensional and three-dimensional bin packing, where both the bin and the items have sizes in two or three dimensions.

Three sources (groups) of benchmark problems are available from the literature for the one dimensional bin packing problem. One of them is from the OR-Library (http://people.brunel.ac.uk/~mastjjb/jeb/orlib/ binpackinfo.html). This group of data sets consists of two classes of problems: uniform and triplet. In the uniform class, the number of items is 120, 250, 500 and 1000 respectively and their sizes are uniformly distributed in the range of [20,100]. The bin capacity is 150. We shall denote these by Fal_U120, Fal_U250, Fal_U500 and Fal_U1000 respectively. There are 20 instances for each problem size and hence 80 problem instances in total. In the triplet class, the bin capacity is 1000 and the item sizes are deliberately generated such that, in the optimal solution, every bin contains exactly three items (one “big” and two “small”) without any residual capacity. The number of the items is 60, 120, 249 and 501 (denoted by Fal_T60, Fal_T120, Fal_T249 and Fal_T501 respectively) and each of them contains 20 instances. This class of data sets is claimed to be more difficult because of the fact that no residual capacity is allowed in any bin in the optimal solution. In (Fleszar and Hindi 2002), 1000 runs of perturbation MBS were implemented before applying their variable neighbourhood search algorithm in order to solve this class of data sets. However, in this paper, we allow the simulated annealing hyper-heuristic to automatically adapt to different classes of problem instances by choosing different heuristics.

The second group of data sets was generated and studied by Scholl et al. (1997) and is available at http://www.wiwi.uni-jena.de/Entscheidung/binpp/index.htm. It contains three sets (denoted by Sch_Set1, Sch_Set2 and Sch_Set3 respectively) and comprises a total of 1210 instances. The lower bounds of these instances are available on the same website. The parameters to create Sch_Set1 and Sch_Set2 include the number of the items (ranging from 50 to 500), bin capacity and the ranges that the items’ sizes are drawn from. Sch_Set1 consists of 720 problem instances and the expected average number of items per bin is no larger than three. However, in Sch_Set2, the average number of items per bin varies between three, five, seven and nine. The data sets Sch_Set3 are considered to be harder problem instances because the item size is drawn from a very large range such that no two items have the same size. Only 10 instances are included in this set.

The third group of benchmark data sets are maintained by the EURO Special Interest Group on Cutting and Packing and are downloadable from (http://www.apdio.pt/sicup/index.php). This group of data sets represents a collection of difficult instances from a large number of test instances in three publications (Waescher and Gau 1996, Schwerin and Wascher 1997, Belov and Scheithauer 2006). The data sets Sch_Wae1 and Sch_Wae2 consist of 200 instances selected from (Schwerin and Wascher 1997) which are particularly hard for First-Fit-Descent and partially hard for Martello-Toth Procedure (in fact none of these instances can be solved optimally by First-Fit-Descent). The data sets Wae_Gau1 are collections of 17 instances from (Waescher and Gau 1996) which have not yet been solved by either First-Fit-Descent or Martello-Toth Procedure. Note that all the instances in data sets Wae_Gau2 also appear in Wae_Gau1 so they are considered in this paper. The lower bounds of these instances are available from (http://www.inf.puc-rio.br/~alvim/adriana/_les/detbp.pdf).

Publications:
Bai, R., Burke, E. K., Kendall, G. and McCollum, B. 2007. A Simulated Annealing Hyper-heuristic Methodology for Flexible Decision Support, Submitted.

References
Fleszar, K. and K. S. Hindi. 2002. New heuristics for one-dimensional bin-packing. Computers and Operations Research 29(7), 821-839.

Martello, S. and P. Toth. 1990a. Knapsack problems: algorithms and computer implementations. John Wiley & Sons.

Martello, S. and P. Toth. 1990b. Lower bounds and reduction procedures for the bin packing problem. Discrete Applied Mathematics 28, 59-70.

Scholl, A., R. Klein, and C. Jurgens. 1997. BISON: A fast hybrid procedure for exactly solving the one-dimensional bin packing problem. Computers & Operations Research 24(7), 627-645.

Waescher, G. and T. Gau. 1996. Heuristics for the integer one-dimensional cutting stock problem: a computational study. OR Spektrum 18, 131-144.