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

Ibrahim Muter, Zeynep Sezer

Research output: Contribution to journalArticle

1 Citation (Scopus)

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

Fingerprint

Cutting Stock Problem
Column Generation
Implicit Enumeration
Branch-and-price
Knapsack
Formulation
Knapsack Problem
Hybrid Algorithm
Computational Experiments
Cutting stock problem
Methodology
Requirements
Column generation

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

Cite this

Algorithms for the One-Dimensional Two-Stage Cutting Stock Problem. / Muter, Ibrahim; Sezer, Zeynep.

In: European Journal of Operational Research, Vol. 271, No. 1, 16.11.2018, p. 20-32.

Research output: Contribution to journalArticle

@article{f54ce67bc638413fa6bce4edbce59ebb,
title = "Algorithms for the One-Dimensional Two-Stage Cutting Stock Problem",
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.",
keywords = "Column-and-row generation, Cutting, Problems with column-dependent-rows, Two-stage cutting stock problem",
author = "Ibrahim Muter and Zeynep Sezer",
year = "2018",
month = "11",
day = "16",
doi = "10.1016/j.ejor.2018.04.042",
language = "English",
volume = "271",
pages = "20--32",
journal = "European Journal of Operational Research",
issn = "0377-2217",
publisher = "Elsevier",
number = "1",

}

TY - JOUR

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

AU - Muter, Ibrahim

AU - Sezer, Zeynep

PY - 2018/11/16

Y1 - 2018/11/16

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

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

KW - Column-and-row generation

KW - Cutting

KW - Problems with column-dependent-rows

KW - Two-stage cutting stock problem

UR - http://www.scopus.com/inward/record.url?scp=85048724316&partnerID=8YFLogxK

U2 - 10.1016/j.ejor.2018.04.042

DO - 10.1016/j.ejor.2018.04.042

M3 - Article

VL - 271

SP - 20

EP - 32

JO - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 1

ER -