Scenario-Based Robust Optimization for Two-Stage Decision Making Under Binary Uncertainty

References

• Baldacci R, Hadjiconstantinou E, Mingozzi A (2004) An exact algorithm for the capacitated vehicle routing problem based on a two-commodity network flow formulation. Oper. Res. 52(5):723–738.Link, Google Scholar
• Ben-Tal A, Goryashko A, Guslitzer E, Nemirovski A (2004) Adjustable robust solutions of uncertain linear programs. Math. Programming 99(2):351–376.Google Scholar
• Ben-Tal A, Den Hertog D, De Waegenaere A, Melenberg B, Rennen G (2013) Robust solutions of optimization problems affected by uncertain probabilities. Management Sci. 59(2):341–357.Link, Google Scholar
• Benders J (1962) Partitioning procedures for solving mixed-variable programming problems. Numerische Mathematik 4(1):238–252.Google Scholar
• Bertsimas D, Caramanis C (2010) Finite adaptability in multistage linear optimization. IEEE Trans. Automatic Control 55(12):2751–2766.Google Scholar
• Bertsimas D, Copenhaver MS (2018) Characterization of the equivalence of robustification and regularization in linear and matrix regression. Eur. J. Oper. Res. 270(3):931–942.Google Scholar
• Bertsimas D, Den Hertog D (2022) Robust and Adaptive Optimization (Dynamic Ideas LLC, Charlestown, MA).Google Scholar
• Bertsimas D, Dunning I (2016) Multistage robust mixed-integer optimization with adaptive partitions. Oper. Res. 64(4):980–998.Link, Google Scholar
• Bertsimas D, Georghiou A (2015) Design of near optimal decision rules in multistage adaptive mixed-integer optimization. Oper. Res. 63(3):610–627.Link, Google Scholar
• Bertsimas D, Georghiou A (2018) Binary decision rules for multistage adaptive mixed-integer optimization. Math. Programming 167(2):395–433.Google Scholar
• Bertsimas D, Goyal V (2012) On the power and limitations of affine policies in two-stage adaptive optimization. Math. Programming 134(2):491–531.Google Scholar
• Bertsimas D, Kallus N (2020) From predictive to prescriptive analytics. Management Sci. 66(3):1025–1044.Link, Google Scholar
• Bertsimas D, Dunning I, Lubin M (2016) Reformulation vs. cutting-planes for robust optimization. Comput. Management Sci. 13(2):195–217.Google Scholar
• Bertsimas D, Iancu DA, Parrilo PA (2010) Optimality of affine policies in multistage robust optimization. Math. Oper. Res. 35(2):363–394.Link, Google Scholar
• Bertsimas D, Iancu DA, Parrilo PA (2011) A hierarchy of near-optimal policies for multistage adaptive optimization. IEEE Trans. Automatic Control 56(12):2809–2824.Google Scholar
• Bertsimas D, McCord C, Sturt B (2023) Dynamic optimization with side information. Eur. J. Oper. Res. 304(2):634–651.Google Scholar
• Bertsimas D, Shtern S, Sturt B (2022a) A data-driven approach to multistage stochastic linear optimization. Management Sci. 69(1):51–74.Link, Google Scholar
• Bertsimas D, Shtern S, Sturt B (2022b) Two-stage sample robust optimization. Oper. Res. 70(1):624–640.Link, Google Scholar
• Bertsimas D, Sim M, Zhang M (2019) Adaptive distributionally robust optimization. Management Sci. 65(2):604–618.Link, Google Scholar
• Bertsimas D, Litvinov E, Sun XA, Zhao J, Zheng T (2012) Adaptive robust optimization for the security constrained unit commitment problem. IEEE Trans. Power Systems 28(1):52–63.Google Scholar
• Bienstock D, Özbay N (2008) Computing robust basestock levels. Discrete Optim. 5(2):389–414.Google Scholar
• Birge J, Louveaux F (1988) A multicut algorithm for two-stage stochastic linear programs. Eur. J. Oper. Res. 34(3):384–392.Google Scholar
• Birge J, Louveaux F (2011) Introduction to Stochastic Programming (Springer Science & Business Media, New York).Google Scholar
• Buchheim C, Kurtz J (2018) Robust combinatorial optimization under convex and discrete cost uncertainty. EURO J. Comput. Optim. 6(3):211–238.Google Scholar
• Caramanis C, Mannor S, Xu H (2012) 14 robust optimization in machine learning. Sra S, Nowozin S, Wright SJ, eds. Optimization for Machine Learning (MIT Press, Cambridge, MA), 369–404.Google Scholar
• Chan TC, Shen ZJM, Siddiq A (2018) Robust defibrillator deployment under cardiac arrest location uncertainty via row-and-column generation. Oper. Res. 66(2):358–379.Link, Google Scholar
• Chen Z, Sim M, Xiong P (2020) Robust stochastic optimization made easy with RSOME. Management Sci. 66(8):3329–3339.Link, Google Scholar
• Dupačová J, Gröwe-Kuska N, Römisch W (2003) Scenario reduction in stochastic programming. Math. Programming 95(3):493–511.Google Scholar
• Gorissen BL, Yanikoğlu İ, den Hertog D (2015) A practical guide to robust optimization. Omega 53:124–137.Google Scholar
• Hanasusanto GA, Kuhn D, Wiesemann W (2015) K-adaptability in two-stage robust binary programming. Oper. Res. 63(4):877–891.Link, Google Scholar
• Hanasusanto GA, Kuhn D, Wiesemann W (2016) A comment on “computational complexity of stochastic programming problems”. Math. Programming 159(1–2):557–569.Google Scholar
• Henrion R, Römisch W (2022) Problem-based optimal scenario generation and reduction in stochastic programming. Math. Programming 191:183–205.Google Scholar
• Høyland K, Kaut M, Wallace SW (2003) A heuristic for moment-matching scenario generation. Comput. Optim. Appl. 24(2–3):169–185.Google Scholar
• Jagtenberg CJ, Bhulai S, van der Mei RD (2017a) Dynamic ambulance dispatching: Is the closest-idle policy always optimal? Health Care Management Sci. 20(4):517–531.Google Scholar
• Jagtenberg CJ, van den Berg PL, van der Mei RD (2017b) Benchmarking online dispatch algorithms for emergency medical services. Eur. J. Oper. Res. 258(2):715–725.Google Scholar
• Jaillet P (1988) A priori solution of a traveling salesman problem in which a random subset of the customers are visited. Oper. Res. 36(6):929–936.Link, Google Scholar
• Kaggle (2020) https://www.kaggle.com.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.Google Scholar
• Lagos F, Klapp MA, Toriello A (2019) Branch-and-price for routing with probabilistic customers. Working paper, Georgia Institute of Technology, Atlanta.Google Scholar
• Magnanti TL, Wong RT (1981) Accelerating Benders decomposition: Algorithmic enhancement and model selection criteria. Oper. Res. 29(3):464–484.Link, Google Scholar
• Nemirovski A, Shapiro A (2006) Scenario approximations of chance constraints. Calafiore G, Dabbene F, eds. Probabilistic and Randomized Methods for Design under Uncertainty (Springer, London), 3–47.Google Scholar
• Office of City Controller for Pittsburgh (2014) Performance Audit Report for Department of Public Safety Bureau of Emergency Medical Services (Office of City Controller for Pittsburgh, Pittsburgh).Google Scholar
• Prochazka V, Wallace SW (2018) Stochastic programs with binary distributions: Structural properties of scenario trees and algorithms. Comput. Management Sci. 15(3–4):397–410.Google Scholar
• Prochazka V, Wallace SW (2020) Scenario tree construction driven by heuristic solutions of the optimization problem. Comput. Management Sci. 17:277–307.Google Scholar
• Römisch W (2009) Scenario reduction techniques in stochastic programming. Watanabe O, Zeugmann T, eds. Stochastic Algorithms: Foundations and Applications (Springer, Heidelberg, Berlin), 1–14.Google Scholar
• Rousseeuw P, Kaufman P (1987) Clustering by means of medoids. Dodge Y, ed. Proc. Stat. Data Anal. Based on L1 Norm Conf. (Birkhäuser Basel, Neuchatel, Switzerland), 1–12.Google Scholar
• Shaham U, Yamada Y, Negahban S (2015) Understanding adversarial training: Increasing local stability of neural nets through robust optimization. Preprint, submitted November 17, https://arxiv.org/abs/1511.05432.Google Scholar
• Shapiro A, Nemirovski A (2005) On complexity of stochastic programming problems. Jeyakumar V, Rubinov A, eds, Continuous Optimization (Springer, New York), 111–146.Google Scholar
• Shapiro A, Dentcheva D, Ruszczyński A (2014) Lectures on Stochastic Programming: Modeling and Theory (Society for Industrial and Applied Mathematics, Philadelphia).Google Scholar
• Subramanyam A, Gounaris CE, Wiesemann W (2020) K-adaptability in two-stage mixed-integer robust optimization. Math. Programming Comput. 12:193–224.Google Scholar
• University of California at Irvine (2020) UC Irvine machine learning repository. https://archive.ics.uci.edu/ml.Google Scholar
• Van Parys BP, Esfahani PM, Kuhn D (2017) From data to decisions: Distributionally robust optimization is optimal. Preprint, submitted April 13, https://arxiv.org/abs/1704.04118.Google Scholar
• Vayanos P, Kuhn D, Rustem B (2011) Decision rules for information discovery in multi-stage stochastic programming. 50th IEEE Conf. Decision Control Eur. Control Conf. (IEEE, Piscataway, NJ), 7368–7373.Google Scholar
• VRP Web (2020) https://www.bernabe.dorronsoro.es/vrp/.Google Scholar
• Wang K, Jacquillat A (2020) A stochastic integer programming approach to air traffic scheduling and operations. Oper. Res. 68(5):1375–1402.Link, Google Scholar
• Xu H, Caramanis C, Mannor S (2009) Robustness and regularization of support vector machines. J. Machine Learn. Res. 10(7):1485–1510.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.Google Scholar
• Zhang W, Jacquillat A, Wang K, Wang S (2023) Optimized scenario reduction: Solving large-scale stochastic programs with quality guarantees. INFORMS J. Comput. 35(4):711–908.Google Scholar