Computational study of a column generation algorithm for bin packing and cutting stock problems |
| |
Authors: | François Vanderbeck |
| |
Institution: | (1) Mathématiques Appliquées Bordeaux (MAB), Université de Bordeaux 1, 351, Cours de la Libération, F-33405 Talence Cedex, France, e-mail: fv@math.u-bordeaux.fr, Url: http://www.math.u-bordeaux.fr/∼fv, FR |
| |
Abstract: | This paper reports on our attempt to design an efficient exact algorithm based on column generation for the cutting stock
problem. The main focus of the research is to study the extend to which standard branch-and-bound enhancement features such
as variable fixing, the tightening of the formulation with cutting planes, early branching, and rounding heuristics can be
usefully incorporated in a branch-and-price algorithm. We review and compare lower bounds for the cutting stock problem. We
propose a pseudo-polynomial heuristic. We discuss the implementation of the important features of the integer programming
column generation algorithm and, in particular, the implementation of the branching scheme. Our computational results demonstrate
the efficiency of the resulting algorithm for various classes of bin packing and cutting stock problems.
Received October 18, 1996 / Revised version received May 14, 1998?Published online July 19, 1999 |
| |
Keywords: | : integer programming – column generation – bin packing – cutting stock |
本文献已被 SpringerLink 等数据库收录! |
|