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

G. Belov, G. Scheithauer

Research output: Contribution to journalArticleResearchpeer-review

89 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)85-106
Number of pages22
JournalEuropean Journal of Operational Research
Volume171
Issue number1
DOIs
Publication statusPublished - 16 May 2006

Keywords

  • Branch-and-bound
  • Column generation
  • Cutting
  • Cutting planes

Cite this