Exact solution of cutting stock problems using column generation and branch-and-Bound

✍ Scribed by J.M.Valério de Carvalho

• Publisher: John Wiley and Sons
• Year: 1998
• Tongue: English
• Weight: 247 KB
• Volume: 5
• Category: Article
• ISSN: 0969-6016
• DOI: 10.1016/s0969-6016(97)00044-0

✦ Synopsis

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 ¯ow 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.