A Converging Benders’ Decomposition Algorithm for Two-Stage Mixed-Integer Recourse Models

References

• Ahmed S, Cabral FG, da Costa BFP (2020) Stochastic Lipschitz dynamic programming. Math. Programming 191(2):755–793.Crossref, Google Scholar
• Ahmed S, Garcia R (2003) Dynamic capacity acquisition and assignment under uncertainty. Ann. Oper. Res. 124(1–4):267–283.Crossref, Google Scholar
• Ahmed S, Garcia R, Kong N, Ntaimo L, Parija G, Qiu F, Sen S (2015) SIPLIB: A Stochastic Integer Programming Test Problem Library. Accessed August 17, 2021, https://www2.isye.gatech.edu/sahmed/siplib.Google Scholar
• Ahmed S, Tawarmalani M, Sahinidis NV (2004) A finite branch-and-bound algorithm for two-stage stochastic integer programs. Math. Programming 100(2):355–377.Crossref, Google Scholar
• Anger G (1990) Inverse Problems in Differential Equations (Akademie-Verlag, Berlin).Crossref, Google Scholar
• Angulo G, Ahmed S, Dey SS (2016) Improving the integer L-shaped method. INFORMS J. Comput. 28(3):483–499.Link, Google Scholar
• Balas E, Ceria S, Cornuéjols G (1996) Mixed 0-1 programming by lift-and-project in a branch-and-cut framework. Management Sci. 42(9):1229–1246.Link, Google Scholar
• Balas E, Jeroslow RG (1980) Strengthening cuts for mixed integer programs. Eur. J. Oper. Res. 4(4):224–234.Crossref, Google Scholar
• Balas E, Perregaard M (2003) A precise correspondence between lift-and-project cuts, simple disjunctive cuts, and mixed integer Gomory cuts for 0-1 programming. Math. Programming 94(2–3):221–245.Crossref, Google Scholar
• Bansal M, Huang KL, Mehrotra S (2018) Tight second stage formulations in two-stage stochastic mixed integer programs. SIAM J. Optim. 28(1):788–819.Crossref, Google Scholar
• Benders JF (1962) Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik 4(1):238–252.Crossref, Google Scholar
• Boland N, Christiansen J, Dandurand B, Eberhard A, Linderoth J, Luedtke J, Oliveira F (2018) Combining progressive hedging with a Frank–Wolfe method to compute Lagrangian dual bounds in stochastic mixed-integer programming. SIAM J. Optim. 28(2):1312–1336.Crossref, Google Scholar
• Boyd EA (1994) Fenchel cutting planes for integer programs. Oper. Res. 42(1):53–64.Link, Google Scholar
• Boyd EA (1995) On the convergence of Fenchel cutting planes in mixed-integer programming. SIAM J. Optim. 5(2):421–435.Crossref, Google Scholar
• Carøe CC, Schultz R (1999) Dual decomposition in stochastic integer programming. Oper. Res. Lett. 24(1–2):37–45.Crossref, Google Scholar
• Carøe CC, Tind J (1998) L-shaped decomposition of two-stage stochastic programs with integer recourse. Math. Programming 83(1):451–464.Crossref, Google Scholar
• Del Pia A, Weismantel R (2016) Relaxations of mixed integer sets from lattice-free polyhedra. Ann. Oper. Res. 240(1):95–117.Crossref, Google Scholar
• Dyer M, Stougie L (2006) Computational complexity of stochastic programming problems. Math. Programming 106(3):423–432.Crossref, Google Scholar
• Falk JE (1969) Lagrange multipliers and nonconvex programs. SIAM J. Control 7(4):534–545.Crossref, Google Scholar
• Gade D, Küçükyavuz S, Sen S (2014) Decomposition algorithms with parametric Gomory cuts for two-stage stochastic integer programs. Math. Programming 144(1–2):39–64.Crossref, Google Scholar
• Gassmann HI, Ziemba WT, eds. (2013) Stochastic Programming: Applications in Finance, Energy, Planning and Logistics, World Scientific Series in Finance, vol. 4 (World Scientific).Crossref, Google Scholar
• Georghiou A, Tsoukalas A, Wiesemann W (2020) A primal–dual lifting scheme for two-stage robust optimization. Oper. Res. 68(2):572–590.Abstract, Google Scholar
• Kim K, Mehrotra S (2015) A two-stage stochastic integer programming approach to integrated staffing and scheduling with application to nurse management. Oper. Res. 63(6):1431–1451.Link, Google Scholar
• Kleywegt AJ, Shapiro A, Homem-de Mello T (2002) The sample average approximation method for stochastic discrete optimization. SIAM J. Optim. 12(2):479–502.Crossref, Google Scholar
• Küçükyavuz S, Sen S (2017) An introduction to two-stage stochastic mixed-integer programming. INFORMS TutORials Oper. Res., 1–27.Google Scholar
• Laporte G, Louveaux FV (1993) The integer L-shaped method for stochastic integer programs with complete recourse. Oper. Res. Lett. 13(3):133–142.Crossref, Google Scholar
• Louveaux FV, van der Vlerk MH (1993) Stochastic programming with simple integer recourse. Math. Programming 61(1–3):301–325.Crossref, Google Scholar
• Ntaimo L (2010) Disjunctive decomposition for two-stage stochastic mixed-binary programs with random recourse. Oper. Res. 58(1):229–243.Link, Google Scholar
• Ntaimo L (2013) Fenchel decomposition for stochastic mixed-integer programming. J. Global Optim. 55(1):141–163.Crossref, Google Scholar
• Ntaimo L, Tanner MW (2008) Computations with disjunctive cuts for two-stage stochastic mixed 0-1 integer programs. J. Global Optim. 41(3):365–384.Crossref, Google Scholar
• Perregaard M, Balas E (2001) Generating cuts from multiple-term disjunctions. Aardal K, Gerards B, eds. Internat. Conf. Integer Programming Combin. Optim. (Springer-Verlag, London), 348–360.Google Scholar
• Qi Y, Sen S (2017) The ancestral Benders’ cutting plane algorithm with multi-term disjunctions for mixed-integer recourse decisions in stochastic programming. Math. Programming 161(1–2):193–235.Crossref, Google Scholar
• Rockafellar RT (1970) Convex Analysis, no. 28 (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• Rockafellar RT, Wets RJB (2009) Variational Analysis, vol. 317 (Springer).Google Scholar
• Romeijnders W, Schultz R, van der Vlerk MH, Klein Haneveld WK (2016) A convex approximation for two-stage mixed-integer recourse models with a uniform error bound. SIAM J. Optim. 26(1):426–447.Crossref, Google Scholar
• Rudin W (1976) Principles of Mathematical Analysis (McGraw-Hill, New York).Google Scholar
• Schultz R (1995) On structure and stability in stochastic programs with random technology matrix and complete integer recourse. Math. Programming 70(1–3):73–89.Crossref, Google Scholar
• Schultz R, Stougie L, van der Vlerk MH (1998) Solving stochastic programs with integer recourse by enumeration: A framework using Gröbner basis reductions. Math. Programming 83(1–3):229–252.Crossref, Google Scholar
• Sen S, Higle JL (2005) The C3 theorem and a D2 algorithm for large scale stochastic mixed-integer programming: Set convexification. Math. Programming 104(1):1–20.Crossref, Google Scholar
• Sen S, Sherali HD (2006) Decomposition with branch-and-cut approaches for two-stage stochastic mixed-integer programming. Math. Programming 106(2):203–223.Crossref, Google Scholar
• Sherali HD, Fraticelli BMP (2002) A modification of Benders’ decomposition algorithm for discrete subproblems: An approach for stochastic programs with integer recourse. J. Global Optim. 22(1–4):319–342.Crossref, Google Scholar
• Sherali HD, Zhu X (2006) On solving discrete two-stage stochastic programs having mixed-integer first-and second-stage variables. Math. Programming 108(2–3):597–616.Crossref, Google Scholar
• Tardella F (2004) On the existence of polyhedral convex envelopes. Floudas CA, Pardalos PM, eds. Frontiers in Global Optimization (Springer), 563–573.Crossref, Google Scholar
• Tawarmalani M, Sahinidis NV (2002) Convex extensions and envelopes of lower semi-continuous functions. Math. Programming 93(2):247–263.Crossref, Google Scholar
• Trapp AC, Prokopyev OA, Schaefer AJ (2013) On a level-set characterization of the value function of an integer program and its application to stochastic programming. Oper. Res. 61(2):498–511.Link, Google Scholar
• van der Laan N, Romeijnders W (2020) A loose Benders decomposition algorithm for approximating two-stage mixed-integer recourse models. Math. Programming 190(1–2):761–794.Crossref, Google Scholar
• Van Slyke RM, Wets R (1969) L-shaped linear programs with applications to optimal control and stochastic programming. SIAM J. Appl. Math. 17(4):638–663.Crossref, Google Scholar
• Wallace SW, Ziemba WT, eds. (2005) Applications of Stochastic Programming, MPS-SIAM Series on Optimization.Crossref, Google Scholar
• Zeng B, Zhao L (2013) Solving two-stage robust optimization problems using a column-and-constraint generation method. Oper. Res. Lett. 41(5):457–461.Crossref, Google Scholar
• Zhang M, Küçükyavuz S (2014) Finitely convergent decomposition algorithms for two-stage stochastic pure integer programs. SIAM J. Optim. 24(4):1933–1951.Crossref, Google Scholar
• Zou J, Ahmed S, Sun XA (2019) Stochastic dual dynamic integer programming. Math. Programming 175(1–2):461–502.Crossref, Google Scholar