Lower bounds and algorithms for the 2-dimensional vector packing problem

Given n items, each having, say, a weight and a length, and n identical bin s with a weight and a length capacity, the 2-Dimensional Vector Packing Pro blem (2-DVPP) calls for packing all the items into the minimum number of bi ns. The problem is NP-hard, and has applications in loading, scheduling and layout design. As for the closely related Bin Packing Problem (BPP), there are two main possible approaches for the practical solution of 2-DVPP. The first approach is based on lower bounds and heuristics based on combinator ial considerations, which are fast but in some cases not effective enough t o provide optimal solutions when embedded within a branch-and-bound scheme. The second approach is based on an integer programming formulation with a huge number of variables, whose linear programming relaxation can be solved by column generation, typically requiring a considerable time, but obtaini ng extensive information about the optimal solution of the problem. In this paper we first analyze several lower bounds for 2-DVPP. In particular, we determine an upper bound on the worst-case performance of a class of lower bounding procedures derived from BPP. We also prove that the lower bound as sociated with the huge linear programming relaxation dominates all the othe r lower bounds we consider. We then introduce heuristic and exact algorithm s, and report extensive computational results on several instance classes, showing that in some cases the combinatorial approach allows for a fast sol ution of the problem, while in other cases one has to resort to the huge fo rmulation for finding optimal solutions. Our results compare favorably with previous approaches to the problem. (C) 2001 Elsevier Science B.V. All rig hts reserved.