Dynamic-programming-based inequalities for the capacitated lot-sizing problem

Joseph C. Hartman, I. Esra Büyüktahtakin, J. Cole Smith

Research output: Contribution to journalArticle

7 Scopus citations

Abstract

Iterative solutions of forward dynamic programming formulations for the capacitated lot sizing problem are used to generate inequalities for an equivalent integer programming formulation. The inequalities capture convex and concave envelopes of intermediate-stage value functions and can be lifted by examining potential state information at future stages. Several possible implementations that employ these inequalities are tested and it is demonstrated that the proposed approach is more efficient than alternative integer programming-based algorithms. For certain datasets, the proposed algorithm also outperforms a pure dynamic programming algorithm for the problem.

Original languageEnglish (US)
Pages (from-to)915-930
Number of pages16
JournalIIE Transactions (Institute of Industrial Engineers)
Volume42
Issue number12
DOIs
StatePublished - Dec 1 2010
Externally publishedYes

Keywords

  • capacitated lot sizing
  • Dynamic programming
  • integer programming

ASJC Scopus subject areas

  • Industrial and Manufacturing Engineering

Fingerprint Dive into the research topics of 'Dynamic-programming-based inequalities for the capacitated lot-sizing problem'. Together they form a unique fingerprint.

  • Cite this