Bidimensional Packing by Bilinear Programming

摘要

We consider geometric problems in which rectangles have to be packed in (identical) squares, that turn out to be very hard in practice and for which ILP formulations in which variables specify the coordinates in the packing perform very poorly. While most methods developed until the end of last century are based on simple geometric considerations, a recent landmark result of Fekete and Schepers suggests to put these geometric aspects aside and use the most advanced tools for the 1-dimensional case. In this paper we make additional progress in this direction, especially on the basic question "Does a given set of rectangles fit in a square?", that turns out to be the bottleneck of all the approaches known. Given a set of rectangles and the associated convex hull of the incidence vectors of rectangle subsets that fit in a square, we derive a wide class of valid inequalities for this convex hull from a complete description of the two knapsack polytopes associated with the widths and the heights of the rectangles, respectively. Additionally, we illustrate how to solve the associated separation problem as a bilinear program, for which we develop a solution method that turns out to be fast in practice, and show that integer solutions that satisfy all these inequalities generally correspond to vertices of the original convex hull. The same tools are used to derive lower bounds for the 2-dimensional bin packing problem, corresponding to the determination of an optimal pair of so-called dual feasible functions, that in many cases equal the lower bounds obtained by the customary set covering formulation (for which column generation is very hard) being computable within times that are orders of magnitude smaller. All our results extend immediately to the general problem of packing d-dimensional parallelepipeds in hypercubes.