A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting

A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting

0.00 Avg rating0 Votes
Article ID: iaor2007743
Country: Netherlands
Volume: 171
Issue: 1
Start Page Number: 85
End Page Number: 106
Publication Date: May 2006
Journal: European Journal of Operational Research
Authors: ,
Keywords: programming: branch and bound, programming: integer
Abstract:

The one-dimensional cutting stock problem (1D-CSP) and the two-dimensional two-stage guillotine constrained cutting problem (2D-2CP) are considered in this paper. The Gilmore–Gomory models of these problems have very strong continuous relaxations providing a good bound in an LP-based solution approach. In recent years, there have been several efforts to attack the one-dimensional problem by LP-based branch-and-bound with column generation (called branch-and-price) and by general-purpose Chvátal–Gomory cutting planes. In this paper we investigate a combination of both approaches, i.e., the LP relaxation at each branch-and-price node is strengthened by Chvátal–Gomory and Gomory mixed-integer cuts. The branching rule is that of branching on variables of the Gilmore–Gomory formulation. Tests show that, for 1D-CSP, general-purpose cuts are useful only in exceptional cases. However, for 2D-2CP their combination with branching is more effective than either approach alone and mostly better than other methods from the literature.

Reviews

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