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 journalArticlepeer-review

11 Scopus citations


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)
Issue number12
StatePublished - Dec 2010
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Industrial and Manufacturing Engineering


  • Dynamic programming
  • capacitated lot sizing
  • integer programming


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

Cite this