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

Ibrahim Muter, Zeynep Sezer

Research output: Contribution to journalArticle

5 Citations (Scopus)
6 Downloads (Pure)

Abstract

In this paper, we consider a two-stage extension of one-dimensional cutting stock problem which arises when technical requirements inhibit cutting large stock rolls to demanded widths of finished rolls directly. Therefore, demands on finished rolls are fulfilled through two subsequent cutting processes, in which rolls produced in the former are used as input for the latter, while the number of stock rolls used is minimized. We tackle the pattern-based formulation of this problem which typically has a very large number of columns 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.
Original languageEnglish
Pages (from-to)20-32
Number of pages13
JournalEuropean Journal of Operational Research
Volume271
Issue number1
Early online date27 Apr 2018
DOIs
Publication statusPublished - 16 Nov 2018

Keywords

  • Column-and-row generation
  • Cutting
  • Problems with column-dependent-rows
  • Two-stage cutting stock problem

ASJC Scopus subject areas

  • Computer Science(all)
  • Modelling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Fingerprint Dive into the research topics of 'Algorithms for the One-Dimensional Two-Stage Cutting Stock Problem'. Together they form a unique fingerprint.

Cite this