A Branch-and-Cut Method for Dynamic Decision Making Under Joint Chance Constraints

References

• Ahmed S, Shapiro A (2008) Solving chance-constrained stochastic programs via sampling and integer programming. Chen Z-L, Raghavan S, eds. 2008 Tutorials in Operations Research (INFORMS, Hanover, MD), 261–269.Link, Google Scholar
• Ahmed S, Çakmak U, Shapiro A (2007) Coherent risk measures in inventory problems. Eur. J. Oper. Res. 182(1):226–238.Crossref, Google Scholar
• Ahuja RK, Magnanti TL, Orlin JB (1993) Network Flows: Theory, Algorithms, and Applications (Prentice Hall, Englewood Cliffs, NJ).Google Scholar
• Andrieu L, Henrion R, Römisch W (2010) A model for dynamic chance constraints in hydro power reservoir management. Eur. J. Oper. Res. 207(2):579–589.Crossref, Google Scholar
• Atamtürk A, Nemhauser GL, Savelsbergh MWP (2000) The mixed vertex packing problem. Math. Programming 89(1):35–53.Crossref, Google Scholar
• Baker KR (1977) An experimental study of the effectiveness of rolling schedules in production planning. Decision Sci. 8(1):19–27.Crossref, Google Scholar
• Ben-Tal A, Nemirovski A (1998) Robust convex optimization. Math. Oper. Res. 23(4):769–805.Link, Google Scholar
• Ben-Tal A, Nemirovski A (1999) Robust solutions of uncertain linear programs. Oper. Res. Lett. 25(1):1–13.Crossref, Google Scholar
• Ben-Tal A, Nemirovski A (2000) Robust solutions of linear programming problems contaminated with uncertain data. Math. Programming 88(3):411–424.Crossref, Google Scholar
• Ben-Tal A, Boaz G, Shimrit S (2009) Robust multi-echelon multi-period inventory control. Eur. J. Oper. Res. 199(3):922–935.Crossref, Google Scholar
• Beraldi P, Ruszczyński A (2002a) A branch and bound method for stochastic integer programs under probabilistic constraints. Optim. Methods Software 17(3):359–382.Crossref, Google Scholar
• Beraldi P, Ruszczyński A (2002b) The probabilistic set covering problem. Oper. Res. 50(6):956–967.Link, Google Scholar
• Beraldi P, Bruni ME, Conforti D (2004) Designing robust emergency medical service via stochastic programming. Eur. J. Oper. Res. 158(1):183–193.Crossref, Google Scholar
• Bertsimas D, Brown D (2009) Constructing uncentainty sets for robust linear optimization. Oper. Res. 57(6):1483–1495.Link, Google Scholar
• Bertsimas D, Sim M (2003) Robust discrete optimization and network flows. Math. Programming 98(1–3):49–71.Crossref, Google Scholar
• Bertsimas D, Thiele A (2006) A robust optimization approach to inventory theory. Oper. Res. 54(1):150–168.Link, Google Scholar
• Bertsimas D, Iancu D, Parrilo P (2009) A hierarchy of suboptimal policies for the multiperiod, multi-echelon, robust inventory problem. INFORMS MSOM Conf. Proc, Cambridge, MA.Google Scholar
• Bertsimas D, Iancu D, Parrilo P (2010) Optimality of affine policies in multistage robust optimization. Math. Oper. Res. 35(2):363–394.Link, Google Scholar
• Bertsimas D, Iancu D, Parrilo P (2011) A hierarchy of near-optimal policies for multistage adaptive optimization. IEEE Trans. Automatic Control 56(12):2809–2824.Crossref, Google Scholar
• Birge JR, Louveaux F (1997) Introduction to Stochastic Programming (Springer Verlag, New York).Google Scholar
• Bitran GB, Yanasse HH (1982) Computational complexity of the capacitated lot size problem. Management Sci. 28(10):1174–1185.Link, Google Scholar
• Bitran GB, Yanasse HH (1984) Deterministic approximations to stochastic production problems. Oper. Res. 32(5):999–1018.Link, Google Scholar
• Blackburn JD, Millen RA (1980) Heuristic lot-sizing performance in a rolling-schedule environment. Decision Sci. 11(4):691–701.Crossref, Google Scholar
• Bookbinder JH, Tan J (1988) Strategies for the probabilistic lot-sizing problem with service level constraints. Management Sci. 34(9):1096–1108.Link, Google Scholar
• Calafiore GC, Campi MC (2005) Uncertain convex programs: Randomized solutions and confidence levels. Math. Programming 102(1):25–46.Crossref, Google Scholar
• Calafiore GC, Campi MC (2006) The scenario approach to robust control design. IEEE Trans. Automatic Control 51(5):742–753.Crossref, Google Scholar
• Charnes A, Cooper WW (1959) Chance-constrained programming. Management Sci. 6(1):73–79.Link, Google Scholar
• Charnes A, Cooper WW (1963) Deterministic equivalents for optimizing and satisficing under chance constraints. Oper. Res. 11(1):18–39.Link, Google Scholar
• Charnes A, Cooper WW, Symonds GY (1958) Cost horizons and certainty equivalents: An approach to stochastic programming of heating oil. Management Sci. 4(3):235–263.Link, Google Scholar
• Chen W, Sim M, Sun J, Teo C (2010) Implications in joint chance-constrained optimization. Oper. Res. 58(2):570–485.Link, Google Scholar
• Cheon M-S, Ahmed S, Al-Khayyal F (2006) A branch-reduce-cut algorithm for the global optimization of probabilistically constrained linear programs. Math. Programming 108(2–3):617–634.Crossref, Google Scholar
• Dentcheva D (2009) Optimization models with probabilistic constraints. Shapiro A, Dentcheva D, Ruszczyński A, eds. Lectures on Stochastic Programming: Modeling and Theory (Society for Industrial and Applied Mathematics, Philadelphia), 87–154.Crossref, Google Scholar
• Dentcheva D, Ruszczyński A (2008) Stochastic dynamic optimization with discounted stochastic dominance constraints. SIAM J. Control Optim. 47(5):2540–2556.Crossref, Google Scholar
• Dentcheva D, Prékopa A, Ruszczyński A (2000) Concavity and efficient points of discrete distributions in probabilistic programming. Math. Programming 89(1):55–77.Crossref, Google Scholar
• El Ghaoui L, Lebret H (1998) Robust solutions to uncertain semidefinite programs. SIAM J. Optim. 9(1):33–52.Crossref, Google Scholar
• El Ghaoui L, Oustry F, Lebret H (1997) Robust solutions to least-square problems to uncertain data matrices. SIAM J. Matrix Anaysis Appl. 18(4):1035–1064.Crossref, Google Scholar
• Erdoğan E, Iyengar G (2006) Ambiguous chance constrained problems and robust optimization. Math. Programming 107(1–2):37–61.Crossref, Google Scholar
• Gade D, Küçükyavuz S (2013) Formulations for dynamic lot sizing with service levels. Naval Res. Logist. 60(2):87–101.Crossref, Google Scholar
• Guan Y (2011) Stochastic lot-sizing with backlogging: Computational complexity analysis. J. Global Optim. 49(4):651–678.Crossref, Google Scholar
• Guan Y, Miller AJ (2008) Polynomial time algorithms for uncapacitated stochastic lot-sizing problems. Oper. Res. 56(5):1172–1183.Link, Google Scholar
• Günlük O, Pochet Y (2001) Mixing mixed-integer inequalities. Math. Programming 90(3):429–457.Crossref, Google Scholar
• Gurvich I, Luedtke J, Tezcan T (2010) Staffing call centers with uncertain demand forecasts: A chance-constrained optimization approach. Management Sci. 56(7):1093–1115.Link, Google Scholar
• Huang K, Küçükyavuz S (2008) On stochastic lot sizing with random lead times. Oper. Res. Lett. 36(3):303–308.Crossref, Google Scholar
• Kall P, Wallace SW (1994) Stochastic Programming (John Wiley & Sons, Chichester, UK).Google Scholar
• Küçükyavuz S (2012) On mixing sets arising in chance-constrained programming. Math. Programming 132(1–2):31–56.Crossref, Google Scholar
• Küçükyavuz S, Pochet Y (2009) Uncapacitated lot sizing with backlogging: The convex hull. Math. Programming 118(1):151–175.Crossref, Google Scholar
• Lasserre J, Bes C, Roubellat F (1985) The stochastic discrete dynamic lot-sizing problem: An open-loop solution. Oper. Res. 33(3):684–689.Link, Google Scholar
• Lejeune MA, Ruszczyński A (2007) An efficient trajectory method for probabilistic inventory-production-distribution problems. Oper. Res. 55(2):378–394.Link, Google Scholar
• Luedtke J (2011) A branch-and-cut decomposition algorithm for solving general chance-constrained mathematical programs. Optimization Online, http://www.optimization-online.org/DB_HTML/2011/05/3033.html.Google Scholar
• Luedtke J, Ahmed S, Nemhauser G (2010) An integer programming approach for linear programs with probabilistic constraints. Math. Programming 122(2):247–272.Crossref, Google Scholar
• Lulli G, Sen S (2004) Branch-and-price algorithm for multistage stochastic integer programming with application to stochastic batch-sizing problems. Management Sci. 50(6):786–796.Link, Google Scholar
• Miller BL, Wagner HM (1965) Chance constrained programming with joint constraints. Oper. Res. 13(6):930–965.Link, Google Scholar
• Morton TE (1977) Universal planning horizons for generalized convex production scheduling. Oper. Res. 26(6):1046–1058.Link, Google Scholar
• Nahmias S (2005) Production and Operations Analysis (McGraw-Hill, New York).Google Scholar
• Nemirovski A, Shapiro A (2005) Scenario approximation of chance constraints. Calafiore G, Dabbene F, eds. Probabilistic and Randomized Methods for Design Under Uncertainty (Springer, London), 3–48.Google Scholar
• Nemirovski A, Shapiro A (2006) Convex approximations of chance constrained programs. SIAM J. Optim. 17(4):969–996.Crossref, Google Scholar
• Pochet Y, Wolsey LA (1988) Lot-size models with backlogging: Strong reformulations and cutting planes. Math. Programming 40(1):317–335.Crossref, Google Scholar
• Prékopa A (1973) Contributions to the theory of stochastic programming. Math. Programming 4(1):202–221.Crossref, Google Scholar
• Prékopa A (1990) Dual method for the solution of a one-stage stochastic programming problem with random RHS obeying a discrete probability distribution. Math. Methods Oper. Res. 34(6):441–461.Crossref, Google Scholar
• Prékopa A (1995) Stochastic Programming (Kluwer Academic Publishers, Dordrecht, Germany).Crossref, Google Scholar
• Prékopa A (2003) Probabilistic programming. Ruszczyński A, Shapiro A, eds. Handbooks in Operations Research and Management Science, Vol. 10 (Elsevier, Amsterdam), 267–351.Crossref, Google Scholar
• Ruszczyński A (2002) Probabilistic programming with discrete distributions and precedence constrained knapsack polyhedra. Math. Programming 93(2):195–215.Crossref, Google Scholar
• Ruszczyński A, Shapiro A (2006a) Conditional risk mappings. Math. Oper. Res. 31(3):544–561.Link, Google Scholar
• Ruszczyński A, Shapiro A (2006b) Optimization of convex risk functions. Math. Oper. Res. 31(3):433–452.Link, Google Scholar
• Ruszczyński A, Shapiro A (2009) Risk averse optimization. Shapiro A, Dentcheva D, Ruszczyński A, eds. Lectures on Stochastic Programming: Modeling and Theory (Society for Industrial and Applied Mathematics, Philadelphia), 253–332.Crossref, Google Scholar
• Saxena A, Goyal V, Lejeune MA (2010) MIP reformulations of the probabilistic set covering problem. Math. Programming 121(1):1–31.Crossref, Google Scholar
• Sen S (1992) Relaxations for probabilistically constrained programs with discrete random variables. Oper. Res. Lett. 11(2):81–86.Crossref, Google Scholar
• Shapiro A (2009) On a time consistency concept in riskaverse multistage stochastic programming. Oper. Res. Lett. 37(3):143–147.Crossref, Google Scholar
• Shen S, Smith JC, Ahmed S (2010) Expectation and chance-constrained models and algorithms for insuring critical paths. Management Sci. 56(10):1794–1814.Link, Google Scholar
• Soyster AL (1973) Convex programming with set-inclusive constraints and applications to inexact linear programming. Oper. Res. 21(5):1154–1157.Link, Google Scholar
• Tanner MW, Ntaimo L (2010) IIS branch-and-cut for joint chance-constrained stochastic programs and application to optimal vaccine allocation. Eur. J. Oper. Res. 207(1):290–296.Crossref, Google Scholar
• Tayur SR, Thomas RR, Natraj NR (1995) An algebraic geometry algorithm for scheduling in presence of setups and correlated demands. Math. Programming 69(1–3):369–401.Crossref, Google Scholar
• Van Vyve M (2005) The continuous mixing polyhedron. Math. Oper. Res. 30(2):441–452.Link, Google Scholar
• Wagner HM, Whitin TM (1958) Dynamic version of the economic lot size problem. Management Sci. 5(1):89–96.Link, Google Scholar
• Zangwill WI (1966) A deterministic multi-period production scheduling model with backlogging. Management Sci. 13(1):105–119.Link, Google Scholar
• Zymler S, Kuhn D, Rüstem B (2013) Distributionally robust joint chance constraints with second-order moment information. Math. Programming 137(1–2):167–198.Crossref, Google Scholar