Abstract
It is well-known that the economic lot-sizing model is well-solved by dynamic programming. On the other hand, the standard mixed integer programming formulation of this problem leads to a very large duality gap. Here the convex hull of the solutions of the economic lot-sizing model is given. In addition, an alternative formulation as a simple plant location problem is examined, and here too the convex hull of solutions is obtained.
Preview
Unable to display preview. Download preview PDF.
References
I. Barany, T.J. Van Roy and L.A. Wolsey, “Strong formulations for multi-item capacitated lot-sizing”, CORE Discussion Paper No. 8312, Université Catholique de Louvain, Louvain-la-Neuve, Belgium, March 1983.
I. Barany, T.J. Van Roy and L.A. Wolsey, “Uncapacitated lot-sizing: The convex hull of solutions: CORE Discussion Paper No. 8314, Université Catholique de Louvain, Louvain-la-Neuve, Belgium, March 1983.
L.R. Ford and D.R. Fulkerson, Flows in networks (Princeton University Press, Princeton, NJ, 1962).
A. Kolen, “A polynomial time algorithm for solving the set covering problem on a totally balanced matrix”, Report BW 147/81, Mathematisch Centrum, Amsterdam, 1981.
J. Krarup and O. Bilde, “Plant location, set covering an economic lot size: An O(mn) algorithm for structural problems”, in: Numerische Methoden bei Optimierungsaufgaben, Band 3: Optimierung bei grapentheoretische und ganzzahligen Problemen, International Series of Numerical Mathematics (ISNM), Vol. 36, (Birkhäuser-Verlag, Basel und Stuttgart, 1977).
H.M. Wagner and T.M. Whitin, “Dynamic version of the economic lot size model”, Management Science 5 (1958) 89–96.
W.I. Zangwill, “A deterministic multi-period production scheduling model with backlogging”, Management Science 13 (1966), 105–119.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1984 The Mathematical Programming Society, Inc.
About this chapter
Cite this chapter
Barany, I., Van Roy, T., Wolsey, L.A. (1984). Uncapacitated lot-sizing: The convex hull of solutions. In: Korte, B., Ritter, K. (eds) Mathematical Programming at Oberwolfach II. Mathematical Programming Studies, vol 22. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0121006
Download citation
DOI: https://doi.org/10.1007/BFb0121006
Received:
Revised:
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-00914-3
Online ISBN: 978-3-642-00915-0
eBook Packages: Springer Book Archive