Using Geometric Techniques to Improve Dynamic Programming Algorithms for theEconomic Lot-Sizing Problem and Extensions

摘要

The paper discusses two basic geometric techniques that can be used to speed upcertain types of dynamic programs. The authors first present the algorithms in a general form, and then they show how these techniques can be applied to the economic lot-sizing problem and extensions. Furthermore, it is illustrated that the geometric techniques can be used to give elegant and insightful proofs of structural results, like Wagner and Whitin's planning horizon theorem. Finally, the authors present results of computational experiments in which new algorithms for the economic lot-sizing problem are compared with each other, as well as with other algorithms from the literature.