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: | Lee Jon |
Keywords: | programming: integer |
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.