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

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.

Keywords:

• Dynamic programming
• integer programming
• capacitated lot sizing

Acknowledgements

The authors are grateful to two anonymous referees whose remarks led to an improved revision of this article. Dr. Hartman gratefully acknowledges National Science Foundation support under grant CMMI-0813671 and Dr.Smith gratefully acknowledges the support of the Air Force Office of Scientific Research under grants FA9550-07-1-0404 and FA9550-08-1-0189.

[Supplementary materials are available for this article. Go to the publisher's online edition of IIE Transactions for free supplemental resources; see Appendix 2 for a description of the content.]