This Article Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Google Scholar Articles by Kiwiel, K. C.

An Inexact Bundle Approach to Cutting-Stock Problems

Systems Research Institute, 01-447 Warsaw, Poland
kiwiel{at}ibspan.waw.pl

We show that the linear programming relaxation of the cutting-stock problem can be solved efficiently by the recently proposed inexact bundle method. This method saves work by allowing inaccurate solutions to knapsack subproblems. With suitable rounding heuristics, our method solves almost all the cutting-stock instances from the literature.

Key words: nondifferentiable convex optimization; Lagrangian relaxation; integer programming; bundle methods; knapsack problems; cutting stock
History: received April 2005; revised September 2008; accepted February 2009.