Progressive selection method for the coupled lot-sizing and cutting-stock problem

Tao Wu, Kerem Akartunali, Raf Jans, Zhe Liang

Research output: Contribution to journalArticle

7 Citations (Scopus)

Abstract

The coupled lot-sizing and cutting-stock problem has been a challenging and significant problem for industry, and has therefore received sustained research attention. The quality of the solution is a major determinant of cost performance in related production and inventory management systems, and therefore there is intense pressure to develop effective practical solutions. In the literature, a number of heuristics have been proposed for solving the problem. However, the heuristics are limited in obtaining high solution qualities. This paper proposes a new progressive selection algorithm that hybridizes heuristic search and extended reformulation into a single framework. The method has the advantage of generating a strong bound using the extended reformulation, which can provide good guidelines on partitioning and sampling in the heuristic search procedure so as to ensure an efficient solution process. We also analyze per-item and per-period Dantzig-Wolfe decompositions of the problem and present theoretical comparisons. The master problem of the per-period Dantzig-Wolfe decomposition is often degenerate, which results in a tailing-off effect for column generation. We apply a hybridization of Lagrangian relaxation and stabilization techniques to improve the convergence. The discussion is followed by extensive computational tests, where we also perform detailed statistical analyses on various parameters. Comparisons with other methods indicate that our approach is computationally tractable and is able to obtain improved results.
LanguageEnglish
Pages523-543
Number of pages11
JournalINFORMS Journal on Computing
Volume29
Issue number3
Early online date11 Jul 2017
DOIs
Publication statusPublished - 30 Jul 2017

Fingerprint

Cutting Stock Problem
Lot Sizing
Dantzig-Wolfe Decomposition
Heuristic Search
Reformulation
Heuristics
Production Management
Decomposition
Inventory Management
Lagrangian Relaxation
Column Generation
Tailings
Efficient Solution
Partitioning
Determinant
Stabilization
Industry
Sampling
Heuristic search
Cutting stock problem

Keywords

  • operational research
  • lot sizing
  • integer programming
  • cutting stock
  • heuristics
  • column generation

Cite this

@article{d91b059dffc049f28ad436530551f6d0,
title = "Progressive selection method for the coupled lot-sizing and cutting-stock problem",
abstract = "The coupled lot-sizing and cutting-stock problem has been a challenging and significant problem for industry, and has therefore received sustained research attention. The quality of the solution is a major determinant of cost performance in related production and inventory management systems, and therefore there is intense pressure to develop effective practical solutions. In the literature, a number of heuristics have been proposed for solving the problem. However, the heuristics are limited in obtaining high solution qualities. This paper proposes a new progressive selection algorithm that hybridizes heuristic search and extended reformulation into a single framework. The method has the advantage of generating a strong bound using the extended reformulation, which can provide good guidelines on partitioning and sampling in the heuristic search procedure so as to ensure an efficient solution process. We also analyze per-item and per-period Dantzig-Wolfe decompositions of the problem and present theoretical comparisons. The master problem of the per-period Dantzig-Wolfe decomposition is often degenerate, which results in a tailing-off effect for column generation. We apply a hybridization of Lagrangian relaxation and stabilization techniques to improve the convergence. The discussion is followed by extensive computational tests, where we also perform detailed statistical analyses on various parameters. Comparisons with other methods indicate that our approach is computationally tractable and is able to obtain improved results.",
keywords = "operational research, lot sizing, integer programming, cutting stock, heuristics, column generation",
author = "Tao Wu and Kerem Akartunali and Raf Jans and Zhe Liang",
year = "2017",
month = "7",
day = "30",
doi = "10.1287/ijoc.2017.0746",
language = "English",
volume = "29",
pages = "523--543",
journal = "INFORMS Journal on Computing",
issn = "1091-9856",
number = "3",

}

Progressive selection method for the coupled lot-sizing and cutting-stock problem. / Wu, Tao; Akartunali, Kerem; Jans, Raf; Liang, Zhe.

In: INFORMS Journal on Computing, Vol. 29, No. 3, 30.07.2017, p. 523-543.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Progressive selection method for the coupled lot-sizing and cutting-stock problem

AU - Wu, Tao

AU - Akartunali, Kerem

AU - Jans, Raf

AU - Liang, Zhe

PY - 2017/7/30

Y1 - 2017/7/30

N2 - The coupled lot-sizing and cutting-stock problem has been a challenging and significant problem for industry, and has therefore received sustained research attention. The quality of the solution is a major determinant of cost performance in related production and inventory management systems, and therefore there is intense pressure to develop effective practical solutions. In the literature, a number of heuristics have been proposed for solving the problem. However, the heuristics are limited in obtaining high solution qualities. This paper proposes a new progressive selection algorithm that hybridizes heuristic search and extended reformulation into a single framework. The method has the advantage of generating a strong bound using the extended reformulation, which can provide good guidelines on partitioning and sampling in the heuristic search procedure so as to ensure an efficient solution process. We also analyze per-item and per-period Dantzig-Wolfe decompositions of the problem and present theoretical comparisons. The master problem of the per-period Dantzig-Wolfe decomposition is often degenerate, which results in a tailing-off effect for column generation. We apply a hybridization of Lagrangian relaxation and stabilization techniques to improve the convergence. The discussion is followed by extensive computational tests, where we also perform detailed statistical analyses on various parameters. Comparisons with other methods indicate that our approach is computationally tractable and is able to obtain improved results.

AB - The coupled lot-sizing and cutting-stock problem has been a challenging and significant problem for industry, and has therefore received sustained research attention. The quality of the solution is a major determinant of cost performance in related production and inventory management systems, and therefore there is intense pressure to develop effective practical solutions. In the literature, a number of heuristics have been proposed for solving the problem. However, the heuristics are limited in obtaining high solution qualities. This paper proposes a new progressive selection algorithm that hybridizes heuristic search and extended reformulation into a single framework. The method has the advantage of generating a strong bound using the extended reformulation, which can provide good guidelines on partitioning and sampling in the heuristic search procedure so as to ensure an efficient solution process. We also analyze per-item and per-period Dantzig-Wolfe decompositions of the problem and present theoretical comparisons. The master problem of the per-period Dantzig-Wolfe decomposition is often degenerate, which results in a tailing-off effect for column generation. We apply a hybridization of Lagrangian relaxation and stabilization techniques to improve the convergence. The discussion is followed by extensive computational tests, where we also perform detailed statistical analyses on various parameters. Comparisons with other methods indicate that our approach is computationally tractable and is able to obtain improved results.

KW - operational research

KW - lot sizing

KW - integer programming

KW - cutting stock

KW - heuristics

KW - column generation

UR - https://www.informs.org/

U2 - 10.1287/ijoc.2017.0746

DO - 10.1287/ijoc.2017.0746

M3 - Article

VL - 29

SP - 523

EP - 543

JO - INFORMS Journal on Computing

T2 - INFORMS Journal on Computing

JF - INFORMS Journal on Computing

SN - 1091-9856

IS - 3

ER -