New classes of fast lower bounds for bin packing problems

Fekete, Sandor P. and Schepers, Jörg (2001) New classes of fast lower bounds for bin packing problems.
Published in: Mathematical programming : Series A Vol. 91 (1). pp. 11-31.


The bin packing problem is one of the classical NP-hard optimization problems. Even though there are many excellent theoretical results, including polynomial approximation schemes, there is still a lack of methods that are able to solve practical instances optimally. In this paper, we present a fast and simple generic approach for obtaining new lower bounds, based on dual feasible functions. Worst case analysis as well as computational results show that one of our classes clearly outperforms the currently best known ''cheap'' lower bound for the bin packing problem by Martello and Toth, which can be understood as a special case. This indicates the usefulness of our results in a branch-and-bound framework.

Download: [img] Postscript - Preprinted Version
Download (392kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr97-265a
Depositing User: Archive Admin
Date Deposited: 02 Apr 2001 00:00
Last Modified: 19 Jan 2012 12:51