TY - JOUR
T1 - Using geometric techniques to improve dynamic programming algorithms for the economic lot-sizing problem and extensions
AU - van Hoesel, Stan
AU - Wagelmans, Albert
AU - Moerman, Bram
PY - 1994/6/9
Y1 - 1994/6/9
N2 - In this paper we discuss two basic geometric techniques that can be used to speed up certain types of dynamic programs. We first present the algorithms in a general form, and then we 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, we 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.
AB - In this paper we discuss two basic geometric techniques that can be used to speed up certain types of dynamic programs. We first present the algorithms in a general form, and then we 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, we 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.
UR - http://www.scopus.com/inward/record.url?scp=0028769392&partnerID=8YFLogxK
U2 - 10.1016/0377-2217(94)90077-9
DO - 10.1016/0377-2217(94)90077-9
M3 - Article
AN - SCOPUS:0028769392
SN - 0377-2217
VL - 75
SP - 312
EP - 331
JO - European Journal of Operational Research
JF - European Journal of Operational Research
IS - 2
ER -