A branch-and-cut-and-price algorithm for one- and two-dimensional two-staged cutting (stock) problems

Authors: G. Belov, G. Scheithauer

Preprint MATH-NM-03-2003, TU Dresden, March 2003.
Appeared as:
A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting,
in: EJOR 171 (2006)85 - 106.

The one-dimensional cutting stock problem and the two-dimensional two-staged constrained guillotine cutting (knapsack) problem are considered. They can be formulated by column generation. This model has a very tight continuous relaxation which provides a good bound in an LP-based solution approach. We combine a branching scheme and a cutting plane algorithm using Gomory mixed-integer and strengthened Chvatal-Gomory cuts.
Preprint version:
Postscript, PDF,