Dynamic programming approximation algorithms for the capacitated lot-sizing problem | Journal of Global Optimization Skip to main content
Springer Nature Link
Log in

Dynamic programming approximation algorithms for the capacitated lot-sizing problem

  • Published:
Journal of Global Optimization Aims and scope Submit manuscript

Abstract

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

References

  1. Adelman, D., Barz, C.: A unifying approximate dynamic programming model for the economic lot scheduling problem. Math. Oper. Res. 39(2), 374–402 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  2. Atamtürk, A., Muñoz, J.C.: A study of the lot-sizing polytope. Math. Program. 99(3), 443–465 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  3. Bellman, R., Kalaba, R., Kotkin, B.: Polynomial approximation: a new computational technique in dynamic programming: allocation processes. Math. Comput. 17, 155–161 (1963)

    MathSciNet  MATH  Google Scholar 

  4. Bertsekas, D.P.: Dynamic Programming and Optimal Control, 3rd edition, vol. ii. Athena Scientific, Belmont (2011)

    Google Scholar 

  5. Bertsekas, D.P., Tsitsiklis, J.N.: Neuro-dynamic programming: an overview. In: Proceedings of the 34th IEEE Conference on, Decision and Control, 1995., volume 1, pp. 560–564, (1995)

  6. Bitran, G.R., Haas, E.A., Hirofumi, M.: Production planning of style goods with high setup costs and forecast revisions. Oper. Res. 34(2), 226–236 (1986)

    Article  MATH  Google Scholar 

  7. Büyüktahtakın, İ.E.: Dynamic programming via linear programming. In: Cochran Jr, J.J., Cox, L.A., Keskinocak, P., Kharoufeh, J.P., Smith, J.C. (eds.) Wiley Encyclopedia of Operations Research and Management Science. Wiley, Hoboken, NJ (2011)

    Google Scholar 

  8. Büyüktahtakın, İ.E.: Mixed Integer Programming Approaches to Lot-Sizing and Asset Replacement Problems. PhD thesis, Industrial and Systems Engineering, University of Florida, (2009)

  9. Chen, H.D., Hearn, D.W., Lee, C.Y.: A new dynamic programming algorithm for the single item capacitated dynamic lot size model. J. Global Optim. 4(3), 285–300 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  10. Chen, H.-D., Hearn, D.W., Lee, C.-Y.: A dynamic programming algorithm for dynamic lot size models with piecewise linear costs. J. Global Optim. 4(4), 397–413 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  11. Federgruen, A., Tzur, M.: A simple forward algorithm to solve general dynamic lot sizing models with \(n\) periods in \({O}(n \log n)\) or \({O}(n)\) time. Manage. Sci. 37(8), 909–925 (1991)

    Article  MATH  Google Scholar 

  12. Florian, M., Lenstra, J.K., Rinnooy Kan, A.H.G.: Deterministic production planning: algorithms and complexity. Manag. Sci. 26(7), 669–679 (1980)

    Article  MathSciNet  MATH  Google Scholar 

  13. Hartman, J.C., Büyüktahtakın, İ.E., Smith, J.C.: Dynamic-programming-based inequalities for the capacitated lot-sizing problem. IIE Trans. 42(12), 915–930 (2010)

    Article  Google Scholar 

  14. Hudson, D.J.: Least-squares fitting of a polynomial constrained to be either non-negative non-decreasing or convex. J. R. Stat. Soc. Ser. B (Methodol.) 31(1), 113–118 (1969)

    MATH  Google Scholar 

  15. Klabjan, D., Simchi-Levi, D., Song, M.: Robust stochastic lot-sizing by means of histograms. Prod. Oper. Manag. 22(3), 691–710 (2013)

    Article  Google Scholar 

  16. Kleywegt, A.J., Nori, V.S., Savelsbergh, M.W.P.: Dynamic programming approximations for a stochastic inventory routing problem. Transp. Sci. 38, 42–70 (2004)

    Article  Google Scholar 

  17. Küçükyavuz, S.: Mixed-integer optimization approaches for deterministic and stochastic inventory management. In: Geunes, J.P. (ed.) INFORMS TutORials in Operations Research, vol. 8, pp. 90–105. INFORMS, Hanover, MD (2011)

    Google Scholar 

  18. Levi, R., Lodi, A., Sviridenko, M.: Approximation algorithms for the capacitated multi-item lot-sizing problem via flow-cover inequalities. Math. Oper. Res. 33(2), 416–474 (2008)

    MathSciNet  MATH  Google Scholar 

  19. Muggeo, V.M.: Estimating regression models with unknown break-points. Stat. Med. Wiley Online Libr. 22, 3055–3071 (2003)

    Google Scholar 

  20. Nemhauser, G., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley, New York (1988)

    Book  MATH  Google Scholar 

  21. Pochet, Y., Wolsey, L.A.: Solving multi-item lot-sizing problems using strong cutting planes. Manage. Sci. 37(1), 53–67 (1991)

    Article  MATH  Google Scholar 

  22. Pochet, Y., Wolsey, L.A.: Production Planning by Mixed Integer Programming. Springer, Berlin (2006)

    MATH  Google Scholar 

  23. Powell, W.B.: An Approximate Dynamic Programming Approach to Multi-dimensional Knapsack Problems. Wiley, New York (2007)

    Book  Google Scholar 

  24. Powell, W.B.: Perspectives of approximate dynamic programming. Ann. Oper. Res. 1–38 (2012)

  25. Sutton, R., Barto, A.: Reinforcement Learning. MIT Press, Cambridge (1998)

    Google Scholar 

  26. Toriello, A., Nemhauser, G., Savelsbergh, M.: Decomposing inventory routing problems with approximate value functions. Naval Res. Logist. 57(8), 718–727 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  27. Tsitsiklis, J.N., Van Roy, B.: Feature-based methods for largescale dynamic programming. Mach. Learn. 22, 59–94 (1996)

    MATH  Google Scholar 

  28. Van Hoesel, C.P.M., Wagelmans, A.P.M.: Fully polynomial approximation schemes for single-item capacitated economic lot-sizing problems. Math. Oper. Res. 26(2), 339–357 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  29. Wagner, H.M., Whitin, T.M.: Dynamic version of the economic lot size model. Manage. Sci. 5, 89–96 (1958)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgments

We gratefully acknowledge the support of the NSF under Grant No. EPS-0903806 and the state of Kansas through the Kansas Board of Regents, and the Strategic Engineering Research Fellowship (SERF) of the College of Engineering at Wichita State University. We also thank anonymous referees and the associate editor, whose remarks helped to clarify our exposition.

Author information

Authors and Affiliations

  1. Industrial and Manufacturing Engineering, Wichita State University, 1845 N Fairmount, Wichita, KS, 67260-0035, USA

    İ. Esra Büyüktahtakın & Ning Liu

Authors
  1. İ. Esra Büyüktahtakın
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ning Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to İ. Esra Büyüktahtakın.

Appendix

Appendix

See Tables 1, 2, 3, 4 and 5.

Table 1 Summary of experiments for \(f=1000\) and \(T=90\)
Full size table
Table 2 Summary of experiments for \(f=10,000\) and \(T=90\)
Full size table
Table 3 Summary of experiments for \(T=120\)
Full size table
Table 4 Summary of experiments for \(T=150\)
Full size table
Table 5 Summary of experiments for overall averages over \(T=90\), \(T=120\), and \(T=150\)
Full size table

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Büyüktahtakın, İ.E., Liu, N. Dynamic programming approximation algorithms for the capacitated lot-sizing problem. J Glob Optim 65, 231–259 (2016). https://doi.org/10.1007/s10898-015-0349-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-015-0349-5

Keywords

Search

Navigation