Dynamic programming approximation algorithms for the capacitated lot-sizing problem

Esra Büyüktahtakın, Ning Liu

Research output: Contribution to journalArticlepeer-review

10 Scopus citations


This paper provides a new idea for approximating the inventory cost function to be used in a truncated dynamic program for solving the capacitated lot-sizing problem. The proposed method combines dynamic programming with regression, data fitting, and approximation techniques to estimate the inventory cost function at each stage of the dynamic program. The effectiveness of the proposed method is analyzed on various types of the capacitated lot-sizing problem instances with different cost and capacity characteristics. Computational results show that approximation approaches could significantly decrease the computational time required by the dynamic program and the integer program for solving different types of the capacitated lot-sizing problem instances. Furthermore, in most cases, the proposed approximate dynamic programming approaches can accurately capture the optimal solution of the problem with consistent computational performance over different instances.

Original languageEnglish (US)
Pages (from-to)231-259
Number of pages29
JournalJournal of Global Optimization
Issue number2
StatePublished - Jun 1 2016
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Control and Optimization
  • Applied Mathematics
  • Business, Management and Accounting (miscellaneous)
  • Computer Science Applications
  • Management Science and Operations Research


  • Approximate dynamic programming
  • Approximation algorithms
  • Capacitated lot-sizing
  • Data fitting
  • Mixed-integer programming
  • Production and inventory control


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

Cite this