In Situ Column Generation for a Cutting-Stock Problem

Jon Lee (jonleeus.ibm.com)

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. 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.

Keywords: integer program, column generation, cutting stock

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Category 3: Applications -- OR and Management Sciences (Production and Logistics )

Citation: IBM Research Report RC23589

Download: [PDF]

Entry Submitted: 04/21/2005
Entry Accepted: 04/22/2005
Entry Last Modified: 04/22/2005

Modify/Update this entry