The two-dimensional bin packing problem with variable bin sizes and costs

The two-dimensional variable sized bin packing problem (2DVSBPP) is the problem of packing a set of rectangular items into a set of rectangular bins. The bins have different sizes and different costs, and the objective is to minimize the overall cost of bins used for packing the rectangles. We present an integer-linear formulation of the 2DVSBPP and introduce several lower bounds for the problem. By using Dantzig-Wolfe decomposition we are able to obtain lower bounds of very good quality. The LP-relaxation of the decomposed problem is solved through delayed column generation, and an exact algorithm based on branch-and-price is developed. The paper is concluded with a computational study, comparing the tightness of the various lower bounds, as well as the performance of the exact algorithm for instances with up to 100 items.