A recent breakthrough in the study of multidimensional packing problems was the observation that the so-called dual feasible functions (also called weighting functions), which are widely used for the monodimensional case, could also be used to compute lower bounds in higher dimension. This led, for instance, to a simplification and strengthening of the worst-case analysis of some approximation algorithms. The use of dual feasible functions was also useful in the design of faster exact algorithms. So far, however, the choice of the dual feasible functions to use in this cases was limited to a (small) number of predefined ones.
In this talk, we study the following problem: Given a bidimensional bin packing problem, determine the pair of dual feasible functions (one associated with the widths and the other with the heights of the rectangles) leading to the best lower bound. This problem turns out to be a disjoint bilinear programming problem, that we solve by branch and bound. The lower bounds computed show for the first time that the best known solutions for a number of instances in the literature are actually optimal.
Last modified: Mon Sep 23 18:53:51 CEST 2004