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.
A branch-and-cut-and-price algorithm for one-dimensional
stock cutting and two-dimensional two-stage cutting,
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.