Optimization Online


In Situ Column Generation for a Cutting-Stock Problem

Jon Lee (jonlee***at***us.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society