In situ column generation for a cutting-stock problem

In situ column generation for a cutting-stock problem

0.00 Avg rating0 Votes
Article ID: iaor20083122
Country: United Kingdom
Volume: 34
Issue: 8
Start Page Number: 2345
End Page Number: 2358
Publication Date: Aug 2007
Journal: Computers and Operations Research
Authors:
Keywords: programming: integer
Abstract:

Working with an integer bilinear programming formulation of a one-dimensional cutting-stock problem, we develop an ILP-based local-search heuristic. The ILPs holistically integrate the master and subproblem of the usual price driven pattern-generation paradigm, resulting in a unified model that generates new patterns in situ. We work harder to generate new columns, but we are guaranteed that new columns give us an integer linear-programming improvement (rather than the continuous linear-programming improvement sought by the usual price driven column generation). The method is well suited to practical restrictions such as when a limited number of cutting patterns should be employed, and our goal is to generate a profile of solutions trading off trim loss against the number of patterns utilized. We describe our implementation and results of computational experiments on instances from a chemical-fiber company.

Reviews

Required fields are marked *. Your email address will not be published.