New stabilization procedures for the cutting stock problem
François Clautiaux, Cláudio Alves, José Valério de Carvalho, Jürgen Rietz
INFORMS Journal on Computing, vol. 23, n.o 4, pp. 530-545, 2011
ABSTRACT
In this paper, we deal with a column generation based
algorithm for the classical cutting stock problem. This
algorithm is known to have convergence issues, which are
addressed in this paper. Our methods are based on the fact
that there are interesting characterizations of the
structure of the dual problem, and that a large number of
dual solutions are known. First we describe methods based
on the concept of dual cuts, proposed by
Valério de Carvalho (2005).
We introduce a general framework for deriving cuts, and we
describe a new type of dual cuts, which exclude solutions
that are linear combinations of some other known
solutions. We also explore new lower and upper bounds for
the dual variables. Then we show how the prior knowledge of a good dual solution helps improving the results. It tightens the bounds around the dual values, and makes the search converge faster if a solution is sought in its neighborhood first. A set of computational experiments on very hard instances are reported at the end of the paper. They confirm the effectiveness of the methods
proposed.
BIBTEX ENTRY
@article{ClautiauxAlvesCarvalhoRietzIJOC11,
author = {Fran\c{c}ois Clautiaux and Cl{\'a}udio Alves and Jos{\'e} Val{\'e}rio de Carvalho and and J{\"u}rgen Rietz},
title = {New stabilization procedures for the cutting stock problem},
journal = {INFORMS Journal on Computing},
volume = {23},
number = {4},
year = {2011},
pages = {530-545} }