Optimization Online


Algorithms for the One-Dimensional Two-Stage Cutting Stock Problem

Ibrahim Muter(i.muter***at***bath.ac.uk)
Zeynep Sezer(zeynep.sezer***at***bahcesehir.edu.tr)

Abstract: In this paper, we consider the two-stage extension of the one-dimensional cutting stock problem which arises when technical requirements inhibit the cutting of large stock rolls to demanded widths of finished rolls directly. Therefore, the demands on finished rolls are fulfilled through two subsequent cutting processes, in which the rolls produced in the former are used as an input for the latter, while the number of stock rolls used is minimized.We tackle the pattern-based formulation of this problem which has exponentially many variables and constraints. The special structure of this formulation induces both a column-wise and a row-wise increase when solved by column generation. We design an exact simultaneous column-and-row generation algorithm whose novel element is a row-generating subproblem that generates a set of columns and rows. For this subproblem, which is modeled as an unbounded knapsack problem, we propose three algorithms: implicit enumeration, column generation which renders the overall methodology nested column generation, and a hybrid algorithm. The latter two are integrated in a well-known knapsack algorithm which forges a novel branch-and-price algorithm for the row-generating subproblem. Extensive computational experiments are conducted, and performances of the three algorithms are compared.

Keywords: two-stage cutting stock problem; column-and-row generation; problems with column-dependent-rows.

Category 1: Applications -- OR and Management Sciences

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

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


Download: [PDF]

Entry Submitted: 11/24/2017
Entry Accepted: 11/24/2017
Entry Last Modified: 11/24/2017

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 Optimization Society