Abstract
This paper addresses a multi-stage stochastic integer programming formulation of the uncapacitated lot-sizing problem under uncertainty. We show that the classical (ℓ,S) inequalities for the deterministic lot-sizing polytope are also valid for the stochastic lot-sizing polytope. We then extend the (ℓ,S) inequalities to a general class of valid inequalities, called the inequalities, and we establish necessary and sufficient conditions which guarantee that the inequalities are facet-defining. A separation heuristic for inequalities is developed and incorporated into a branch-and-cut algorithm. A computational study verifies the usefulness of the inequalities as cuts.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Aggarwal, A., Park, J.K.: Improved algorithms for economic lot size problems. Oper. Res. 41, 549–571 (1993)
Aghezzaf, E.H., Wolsey, L.A.: Modelling piecewise linear concave costs in a tree partitioning problem. Discrete Applied Mathematics 50, 101–109 (1994)
Ahmed, S., King, A., Parija, G.: A multi-stage stochastic integer programming approach for capacity expansion under uncertainty. J. Global Optimization 26, 3–24 (2003)
Ahmed, S., Sahinidis, N.V.: An approximation scheme for stochastic integer programs arising in capacity expansion. Oper. Res. 51, 461–471 (2003)
Atamtürk, A., Kucukyavuz, S.: Lot sizing with inventory bounds and fixed charges. Oper. Res. To appear, 2005
Atamtürk, A., Muñoz, J.C.: A study of the lot-sizing polytope. Math. Program. 99, 443–465 (2004)
Barany, I., Van Roy, T., Wolsey, L.A.: Uncapacitated lot-sizing: The convex hull of solutions. Math. Program. Study 22, 32–43 (1984)
Barany, I., Van Roy, T., Wolsey, L.A.: Strong formulations for multi-item capacitated lot sizing. Management Science 30, 1255–1262 (1984)
Beraldi, P., Ruszczyński, A.: A branch and bound method for stochastic integer problems under probabilistic constraints. Optimization Methods and Software 17, 359–382 (2002)
Federgruen, A., Tzur, M.: A simple forward algorithm to solve general dynamic lot sizing models with n periods in (n log n) or (n) time. Management Science 37, 909–925 (1991)
Guan, Y.: A polyhedral study for stochastic lot-sizing problems. Ph.D. dissertation, Georgia Institute of Technology. Pairing inequalities and stochastic lot-sizing. A study in integer programming
Guan, Y., Ahmed, S., Miller, A.J., Nemhauser, G.L.: Formulations and two-period study for the stochastic uncapacitated lot-sizing problem. On formulations of the stochastic uncapacitated lot-sizing problem. Submitted for publication, 2005
Haugen, K.K., Løkketangen, A., Woodruff, D.L.: Progressive hedging as a meta-heuristic applied to stochastic lot-sizing. European Journal of Operations Research 132, 103–109 (2001)
Leung, J.M.Y., Magnanti, T.L., Vachani, R.: Facets and algorithms for capacitated lot-sizing. Mathematical Programming 45, 331–359 (1989)
Loparic, M., Pochet, Y., Wolsey, L.A.: The uncapacitated lot-sizing problem with sales and safety stocks. Math. Program. 89, 487–504 (2001)
Lulli, G., Sen, S.: A branch-and-price algorithm for multi-stage stochastic integer programming with application to stochastic batch-sizing problems. Working paper, Department of Systems and Industrial Engineering, University of Arizona, Tucson, AZ, 2003
Miller, A.J.: Polyhedral Approaches to Capacitated Lot-Sizing Problems. Ph.D. dissertation, Georgia Institute of Technology, 1999
Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. John Wiley & Sons, 1988
Pochet, Y.: Valid inequalities and separation for capacitated economic lot sizing. Oper. Res. Lett. 7, 109–115 (1988)
Pochet, Y., Wolsey, L.A.: Lot-sizing with constant batches: Formulation and valid inequalities. Mathe. Oper. Res. 18, 767–785 (1993)
Ruszczyński, A., Shapiro, A. (eds): Stochastic Programming. Handbooks in Operations Research and Management Science 10. Elsevier, 2003.
Van Hoesel, C.P.M., Wagelmans, A.P.M., Wolsey, L.A.: Polyhedral characterization of the economic lot-sizing problem with start-up costs. SIAM J. Discrete Math. 7, 141–151 (1994)
Wagelmans, A., van Hoesel, A., Kolen, A.: Economic lot sizing: An (n log n) algorithm that runs in linear time in the Wagner-Whitin case. Oper. Res. 40, 145–156 (1992)
Wagner, H.M., Whitin, T.M.: Dynamic version of the economic lot size model. Management Science 5, 89–96 (1958)
Author information
Authors and Affiliations
Corresponding author
Additional information
This research has been supported in part by the National Science Foundation under Award number DMII-0121495.
Rights and permissions
About this article
Cite this article
Guan, Y., Ahmed, S., Nemhauser, G. et al. A branch-and-cut algorithm for the stochastic uncapacitated lot-sizing problem. Math. Program. 105, 55–84 (2006). https://doi.org/10.1007/s10107-005-0572-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-005-0572-9