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

82 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

@article{1e0b23f39e854a5b83505b4874e88c42,
title = "A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting",
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{\'a}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{\'a}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.",
keywords = "Branch-and-bound, Column generation, Cutting, Cutting planes",
author = "G. Belov and G. Scheithauer",
year = "2006",
month = "5",
day = "16",
doi = "10.1016/j.ejor.2004.08.036",
language = "English",
volume = "171",
pages = "85--106",
journal = "European Journal of Operational Research",
issn = "0377-2217",
publisher = "Elsevier",
number = "1",

}

A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting. / Belov, G.; Scheithauer, G.

In: European Journal of Operational Research, Vol. 171, No. 1, 16.05.2006, p. 85-106.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

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

AU - Belov, G.

AU - Scheithauer, G.

PY - 2006/5/16

Y1 - 2006/5/16

N2 - 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.

AB - 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.

KW - Branch-and-bound

KW - Column generation

KW - Cutting

KW - Cutting planes

UR - http://www.scopus.com/inward/record.url?scp=28044443917&partnerID=8YFLogxK

U2 - 10.1016/j.ejor.2004.08.036

DO - 10.1016/j.ejor.2004.08.036

M3 - Article

VL - 171

SP - 85

EP - 106

JO - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 1

ER -