The Cutting Stock Problem: A new model based on hypergraph flows

The Cutting Stock Problem is a classic integer linear programming problem, which has a host of different interesting applications. Two main approaches can be followed for its soution: heuristics, and linear programming relaxations. In this paper, a new linear programming algorithm for the One-Dimensional Cutting Stock problem is suggested. The algorithm is based on the formulation of the linear programming relaxation in terms of minimum cost flows on hypergraphs, for which a hypergraph simplex algorithm has been recently proposed. Based on the hypergraph model, a specialization of the hypergraph simplex algorithm is proposed for solving the Cutting Stock relaxation, which uses the ‘delayed pattern generation’ idea to maintain only sub-hypergraphs at each pivot operation. The bound so found is then rounded out to provide an integer solution. Preliminary results, obtained by means of a LISP implementation of the algorithm which has been developed for an Italian steel factory, are quite intersting: large instances are in fact solved in a reasonable amount of time, often providing an integer solution. A wider experimentation is in progress.