A polyhedral study of multiechelon lot sizing with intermediate demands

Minjiao Zhang*, Simge Küçükyavuz, Hande Yaman

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

30 Scopus citations

Abstract

In this paper, we study a multiechelon uncapacitated lot-sizing problem in series (m-ULS), where the output of the intermediate echelons has its own external demand and is also an input to the next echelon. We propose a polynomial-time dynamic programming algorithm, which gives a tight, compact extended formulation for the two-echelon case (2-ULS). Next, we present a family of valid inequalities for m-ULS, show its strength, and give a polynomial-time separation algorithm. We establish a hierarchy between the alternative formulations for 2-ULS. In particular, we show that our valid inequalities can be obtained from the projection of the multicommodity formulation. Our computational results show that this extended formulation is very effective in solving our uncapacitated multi-item two-echelon test problems. In addition, for capacitated multi-item, multiechelon problems, we demonstrate the effectiveness of a branch-and-cut algorithm using the proposed inequalities.

Original languageEnglish (US)
Pages (from-to)918-935
Number of pages18
JournalOperations Research
Volume60
Issue number4
DOIs
StatePublished - Jul 2012

ASJC Scopus subject areas

  • Computer Science Applications
  • Management Science and Operations Research

Fingerprint

Dive into the research topics of 'A polyhedral study of multiechelon lot sizing with intermediate demands'. Together they form a unique fingerprint.

Cite this