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

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

0.00 Avg rating0 Votes
Article ID: iaor2006349
Country: Netherlands
Volume: 2
Issue: 2
Start Page Number: 154
End Page Number: 167
Publication Date: Jun 2005
Journal: Discrete Optimization
Authors: ,
Keywords: programming: linear
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.