Formulations and theoretical analysis of the one-dimensional multi-period cutting stock problem with setup cost

Eduardo M. Silva; Gislaine M. Melega; Kerem Akartunali; Silvio A. de Araujo

doi:10.1016/j.ejor.2022.04.023

Formulations and theoretical analysis of the one-dimensional multi-period cutting stock problem with setup cost

Eduardo M. Silva, Gislaine M. Melega, Kerem Akartunali, Silvio A. de Araujo

Management Science

Research output: Contribution to journal › Article › peer-review

11 Citations (Scopus)

14 Downloads (Pure)

Abstract

In this paper, we study the one-dimensional multi-period cutting stock problem with setup costs on cutting patterns. We present pattern-based and pseudo-polynomial formulations for the problem. Reformulations are also proposed to improve the lower bounds. We then present a thorough theoretical analysis to establish the strength of the various proposed formulations in comparison to each other. Finally, a computational analysis is conducted to complement the theoretical analysis and provide further insights with respect to the complexity and strength of the formulations.

Original language	English
Pages (from-to)	443-460
Number of pages	18
Journal	European Journal of Operational Research
Volume	304
Issue number	2
Early online date	22 Apr 2022
DOIs	https://doi.org/10.1016/j.ejor.2022.04.023
Publication status	Published - 16 Jan 2023

Keywords

combinatorial optimization
cutting
cutting pattern setups
strong reformulations

Access to Document

10.1016/j.ejor.2022.04.023

Silva-etal-EJOR-2022-Formulations-and-theoretical-analysis-of-the-one-dimensional-multi-period-cutting-stock-problemAccepted author manuscript, 961 KBLicence: CC BY-NC-ND 4.0

Multi-Level Robust Optimization: Theory, Algorithms and Practice
Akartunali, K. (Principal Investigator) & Barlow, E. (Co-investigator)
Air Force Office of Scientific Research AFOSR (the)
20/08/18 → 19/08/21
Project: Research - Studentship

São Paulo State University (UNESP)
Akartunali, K. (Visiting researcher)
7 Aug 2018 → 10 Aug 2018
Activity: Visiting an external institution types › Visiting an external academic institution

Cite this

@article{167d6269a32e4e489a72112e72c1f6bd,

title = "Formulations and theoretical analysis of the one-dimensional multi-period cutting stock problem with setup cost",

abstract = "In this paper, we study the one-dimensional multi-period cutting stock problem with setup costs on cutting patterns. We present pattern-based and pseudo-polynomial formulations for the problem. Reformulations are also proposed to improve the lower bounds. We then present a thorough theoretical analysis to establish the strength of the various proposed formulations in comparison to each other. Finally, a computational analysis is conducted to complement the theoretical analysis and provide further insights with respect to the complexity and strength of the formulations.",

keywords = "combinatorial optimization, cutting, cutting pattern setups, strong reformulations",

author = "Silva, {Eduardo M.} and Melega, {Gislaine M.} and Kerem Akartunali and {de Araujo}, {Silvio A.}",

year = "2023",

month = jan,

day = "16",

doi = "10.1016/j.ejor.2022.04.023",

language = "English",

volume = "304",

pages = "443--460",

journal = "European Journal of Operational Research",

issn = "0377-2217",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

T1 - Formulations and theoretical analysis of the one-dimensional multi-period cutting stock problem with setup cost

AU - Silva, Eduardo M.

AU - Melega, Gislaine M.

AU - Akartunali, Kerem

AU - de Araujo, Silvio A.

PY - 2023/1/16

Y1 - 2023/1/16

N2 - In this paper, we study the one-dimensional multi-period cutting stock problem with setup costs on cutting patterns. We present pattern-based and pseudo-polynomial formulations for the problem. Reformulations are also proposed to improve the lower bounds. We then present a thorough theoretical analysis to establish the strength of the various proposed formulations in comparison to each other. Finally, a computational analysis is conducted to complement the theoretical analysis and provide further insights with respect to the complexity and strength of the formulations.

AB - In this paper, we study the one-dimensional multi-period cutting stock problem with setup costs on cutting patterns. We present pattern-based and pseudo-polynomial formulations for the problem. Reformulations are also proposed to improve the lower bounds. We then present a thorough theoretical analysis to establish the strength of the various proposed formulations in comparison to each other. Finally, a computational analysis is conducted to complement the theoretical analysis and provide further insights with respect to the complexity and strength of the formulations.

KW - combinatorial optimization

KW - cutting

KW - cutting pattern setups

KW - strong reformulations

U2 - 10.1016/j.ejor.2022.04.023

DO - 10.1016/j.ejor.2022.04.023

M3 - Article

SN - 0377-2217

VL - 304

SP - 443

EP - 460

JO - European Journal of Operational Research

JF - European Journal of Operational Research

IS - 2

ER -

Formulations and theoretical analysis of the one-dimensional multi-period cutting stock problem with setup cost

Abstract

Keywords

Access to Document

Fingerprint

Projects

Multi-Level Robust Optimization: Theory, Algorithms and Practice

Activities

São Paulo State University (UNESP)

Cite this