Exact Solution of Cutting Stock Problems Using Column Generation and Branch-and-Bound |
| |
Authors: | JM Valério de Carvalho |
| |
Affiliation: | Departamento Produção e Sistemas, Universidade do Minho, 4719 Braga, Portugal |
| |
Abstract: | This paper describes an attempt to solve the one-dimensional cutting stock problem exactly, using column generation and branch-and-bound. A new formulation is introduced for the one-dimensional cutting stock problem that uses general integer variables, not restricted to be binary. It is an arc flow formulation with side constraints, whose linear programming relaxation provides a strong lower bound. In this model, a cutting pattern, which corresponds to a path, is decomposed into single arc variables. The decomposition serves the purpose of showing that it is possible to combine the branch-and-bound method with variable generation. Computational times are reported for one-dimensional cutting stock instances with a number of orders up to 30. |
| |
Keywords: | cutting stock column generation branch-and-bound |
|
|