A hybrid algorithm for the one-dimensional cutting stock problem
Glauber Ferreira Cintra (glauber@ime.usp.br) and Yoshiko Wakabayashi
(yw@ime.usp.br)
Abstract
We present a hybrid algorithm for the one-dimensional cutting stock
problem (CSP) that combines the column generation method and an exact
algorithm. The exact algorithm we describe is appropriate to solve small
instances of the CSP when we know previously a lower bound for the value
of the optimal integer solution. The proposed hybrid algorithm finds an
integer solution whose objective value differs from the optimal value by
at most 1, under the assumption that the MIRUP (Modified Integer Round-Up
Property) conjecture is true. Variations are proposed for the hybrid
algorithm to speed up its runtime. Computational results showing a very
satisfactory performance of our code on a large number of real world and
randomly generated instances are presented.
Última modificação: 29 Mar 2005 às 10:34:07
