An Inexact Bundle Approach to Cutting-Stock Problems

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.