TY - JOUR
T1 - Dynamic programming approximation algorithms for the capacitated lot-sizing problem
AU - Büyüktahtakın, Esra
AU - Liu, Ning
N1 - Funding Information:
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.
Publisher Copyright:
© 2015, Springer Science+Business Media New York.
PY - 2016/6/1
Y1 - 2016/6/1
N2 - 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.
AB - 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.
KW - Approximate dynamic programming
KW - Approximation algorithms
KW - Capacitated lot-sizing
KW - Data fitting
KW - Mixed-integer programming
KW - Production and inventory control
UR - http://www.scopus.com/inward/record.url?scp=84939825261&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84939825261&partnerID=8YFLogxK
U2 - 10.1007/s10898-015-0349-5
DO - 10.1007/s10898-015-0349-5
M3 - Article
AN - SCOPUS:84939825261
SN - 0925-5001
VL - 65
SP - 231
EP - 259
JO - Journal of Global Optimization
JF - Journal of Global Optimization
IS - 2
ER -