On the equivalence of strong formulations for capacitated multi-level lot sizing problems with setup times

Tao Wu, Leyuan Shi, Joseph Geunes, Kerem Akartunali

Research output: Contribution to journalArticle

13 Citations (Scopus)

Abstract

Several mixed integer programming formulations have been proposed for
modeling capacitated multi-level lot sizing problems with setup times. These formulations include the so-called facility location formulation, the shortest route formulation, and the inventory and lot sizing formulation with (l,S) inequalities. In this paper, we demonstrate the equivalence of these formulations when the integrality requirement is relaxed for any subset of binary setup decision variables. This equivalence has significant implications for decomposition-based methods since same optimal solution values are obtained no matter which formulation is used. In particular, we discuss the relax-and-fix method, a decomposition-based heuristic used for the efficient solution of hard lot sizing problems. Computational tests allow us to compare the effectiveness of different formulations using benchmark problems. The choice of formulation directly affects the required computational effort, and our results therefore provide guidelines on choosing an effective formulation during the development of heuristic-based solution procedures.
LanguageEnglish
Pages615-639
Number of pages25
JournalJournal of Global Optimization
Volume53
Issue number4
Early online date31 May 2011
DOIs
Publication statusPublished - Aug 2012

Fingerprint

Lot Sizing
Setup Times
Equivalence
Decomposition
Formulation
Integer programming
Lot sizing
Setup times
Heuristics
Decompose
Facility Location
Integrality
Mixed Integer Programming
Efficient Solution
Optimal Solution
Binary
Benchmark
Subset

Keywords

  • equivalence
  • strong formulation
  • capacitated
  • multi-level lot
  • sizing problems
  • setup times

Cite this

@article{c03e9f2179074b13af9d6e83e54ad75f,
title = "On the equivalence of strong formulations for capacitated multi-level lot sizing problems with setup times",
abstract = "Several mixed integer programming formulations have been proposed formodeling capacitated multi-level lot sizing problems with setup times. These formulations include the so-called facility location formulation, the shortest route formulation, and the inventory and lot sizing formulation with (l,S) inequalities. In this paper, we demonstrate the equivalence of these formulations when the integrality requirement is relaxed for any subset of binary setup decision variables. This equivalence has significant implications for decomposition-based methods since same optimal solution values are obtained no matter which formulation is used. In particular, we discuss the relax-and-fix method, a decomposition-based heuristic used for the efficient solution of hard lot sizing problems. Computational tests allow us to compare the effectiveness of different formulations using benchmark problems. The choice of formulation directly affects the required computational effort, and our results therefore provide guidelines on choosing an effective formulation during the development of heuristic-based solution procedures.",
keywords = "equivalence, strong formulation, capacitated, multi-level lot, sizing problems, setup times",
author = "Tao Wu and Leyuan Shi and Joseph Geunes and Kerem Akartunali",
year = "2012",
month = "8",
doi = "10.1007/s10898-011-9728-8",
language = "English",
volume = "53",
pages = "615--639",
journal = "Journal of Global Optimization",
issn = "0925-5001",
number = "4",

}

On the equivalence of strong formulations for capacitated multi-level lot sizing problems with setup times. / Wu, Tao; Shi, Leyuan; Geunes, Joseph ; Akartunali, Kerem.

In: Journal of Global Optimization, Vol. 53, No. 4, 08.2012, p. 615-639.

Research output: Contribution to journalArticle

TY - JOUR

T1 - On the equivalence of strong formulations for capacitated multi-level lot sizing problems with setup times

AU - Wu, Tao

AU - Shi, Leyuan

AU - Geunes, Joseph

AU - Akartunali, Kerem

PY - 2012/8

Y1 - 2012/8

N2 - Several mixed integer programming formulations have been proposed formodeling capacitated multi-level lot sizing problems with setup times. These formulations include the so-called facility location formulation, the shortest route formulation, and the inventory and lot sizing formulation with (l,S) inequalities. In this paper, we demonstrate the equivalence of these formulations when the integrality requirement is relaxed for any subset of binary setup decision variables. This equivalence has significant implications for decomposition-based methods since same optimal solution values are obtained no matter which formulation is used. In particular, we discuss the relax-and-fix method, a decomposition-based heuristic used for the efficient solution of hard lot sizing problems. Computational tests allow us to compare the effectiveness of different formulations using benchmark problems. The choice of formulation directly affects the required computational effort, and our results therefore provide guidelines on choosing an effective formulation during the development of heuristic-based solution procedures.

AB - Several mixed integer programming formulations have been proposed formodeling capacitated multi-level lot sizing problems with setup times. These formulations include the so-called facility location formulation, the shortest route formulation, and the inventory and lot sizing formulation with (l,S) inequalities. In this paper, we demonstrate the equivalence of these formulations when the integrality requirement is relaxed for any subset of binary setup decision variables. This equivalence has significant implications for decomposition-based methods since same optimal solution values are obtained no matter which formulation is used. In particular, we discuss the relax-and-fix method, a decomposition-based heuristic used for the efficient solution of hard lot sizing problems. Computational tests allow us to compare the effectiveness of different formulations using benchmark problems. The choice of formulation directly affects the required computational effort, and our results therefore provide guidelines on choosing an effective formulation during the development of heuristic-based solution procedures.

KW - equivalence

KW - strong formulation

KW - capacitated

KW - multi-level lot

KW - sizing problems

KW - setup times

U2 - 10.1007/s10898-011-9728-8

DO - 10.1007/s10898-011-9728-8

M3 - Article

VL - 53

SP - 615

EP - 639

JO - Journal of Global Optimization

T2 - Journal of Global Optimization

JF - Journal of Global Optimization

SN - 0925-5001

IS - 4

ER -