On the Optimality of Affine Decision Rules in Distributionally Robust Optimization

References

• Ardestani-Jaafari A, Delage E (2016) Robust optimization of sums of piecewise linear functions with application to inventory problems. Oper. Res. 64(2):474–494.Link, Google Scholar
• Artzner P, Delbaen F, Eber J, Heath D (1999) Coherent measures of risk. Math. Finance 9(3):203–228.Crossref, Google Scholar
• Atamtürk A, Zhang M (2007) Two-stage robust network flow and design under demand uncertainty. Oper. Res. 55(4):662–673.Link, Google Scholar
• Awasthi P, Goyal V, Lu BY (2019) On the adaptivity gap in two-stage robust linear optimization under uncertain constraints. Math. Programming 173(1–2):313–352.Crossref, Google Scholar
• Ayoub J, Poss M (2016) Decomposition for adjustable robust linear optimization subject to uncertainty polytope. Comput. Management Sci. 13(2):219–239.Crossref, Google Scholar
• Babonneau F, Vial JP, Klopfenstein O, Ouorou A (2013) Robust capacity assignment solutions for telecommunications networks with uncertain demands. Networks 62(4):255–272.Crossref, Google Scholar
• Balakrishnan A, Geunes J (2000) Requirements planning with substitutions: Exploiting bill-of-materials flexibility in production planning. Manufacturing Service Oper. Management 2(2):166–185.Link, Google Scholar
• Bampou D, Kuhn D (2011) Scenario-free stochastic programming with polynomial decision rules. Proc. 50th IEEE Conf. Decision Control Eur. Control Conf. (IEEE, Piscataway, NJ), 7806–7812.Google Scholar
• Bapat RB, Raghavan TES (1997) Nonnegative Matrices and Applications (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Ben-Tal A, El Ghaoui L, Nemirovski A (2009) Robust Optimization (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• Ben-Tal A, Chung BD, Mandala SR, Yao T (2011) Robust optimization for emergency logistics planning: Risk mitigation in humanitarian relief supply chains. Transportation Res. Part B 45(8):1177–1189.Crossref, 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.Crossref, 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
• Berman A, Plemmons RJ (1994) Nonnegative Matrices in the Mathematical Sciences (SIAM, Philadelphia).Crossref, Google Scholar
• Bertsimas D, Bidkhori H (2015) On the performance of affine policies for two-stage adaptive optimization: A geometric perspective. Math. Programming 153(2):577–594.Crossref, Google Scholar
• Bertsimas D, Caramanis C (2010) Finite adaptability in multistage linear optimization. IEEE Trans. Automatic Control 55(12):2751–2766.Crossref, Google Scholar
• Bertsimas D, de Ruiter FJCT (2016) Duality in two-stage adaptive linear optimization: Faster computation and stronger bounds. INFORMS J. Comput. 28(3):500–511.Link, 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, Goyal V (2010) On the power of robust solutions in two-stage stochastic and adaptive optimization problems. Math. Oper. Res. 35(2):284–305.Link, 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.Crossref, Google Scholar
• Bertsimas D, Goyal V (2013) On the approximability of adjustable robust convex optimization under uncertainty. Math. Methods Oper. Res. 77(3):323–343.Crossref, Google Scholar
• Bertsimas D, Brown DB, Caramanis C (2011a) Theory and applications of robust optimization. SIAM Rev. 53(3):464–501.Crossref, Google Scholar
• Bertsimas D, Dunning I, Lubin M (2016) Reformulation versus cutting-planes for robust optimization. Comput. Management Sci. 13(2):195–217.Crossref, Google Scholar
• Bertsimas D, Goyal V, Lu BY (2015) A tight characterization of the performance of static solutions in two-stage adjustable robust linear optimization. Math. Programming 150(2):281–319.Crossref, Google Scholar
• Bertsimas D, Goyal V, Sun XA (2011b) A geometric characterization of the power of finite adaptability in multistage stochastic and adaptive optimization. Math. Oper. Res. 36(1):24–54.Link, 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 (2011c) A hierarchy of near-optimal policies for multistage adaptive optimization. IEEE Trans. Automatic Control 56(12):2809–2824.Crossref, Google Scholar
• Bertsimas D, Sim M, Zhang M (2019) Adaptive distributionally robust optimization. Management Sci. 65(2):604–618.Link, Google Scholar
• Birge JR, Louveaux F (2011) Introduction to Stochastic Programming (Springer, New York).Crossref, Google Scholar
• Blankenship JW, Falk JE (1976) Infinitely constrained optimization problems. J. Optim. Theory Appl. 19(2):261–281.Crossref, Google Scholar
• Cacchiani V, Jünger M, Liers F, Lodi A, Schmidt DR (2016) Single-commodity robust network design with finite and Hose demand sets. Math. Programming 157(1):297–342.Crossref, Google Scholar
• Charnes A, Cooper WW, Symonds GH (1958) Cost horizons and certainty equivalents: An approach to stochastic programming of heating oil. Management Sci. 4(3):235–263.Link, Google Scholar
• Chen X, Zhang Y (2009) Uncertain linear programs: Extended affinely adjustable robust counterparts. Oper. Res. 57(6):1469–1482.Link, Google Scholar
• Chen X, Sim M, Sun P, Zhang J (2008) A linear decision-based approximation approach to stochastic programming. Oper. Res. 56(2):344–357.Link, Google Scholar
• Delage E, Iancu D (2015) Robust multistage decision making. INFORMS TutORials Oper. Res. 20–46.Google Scholar
• El Housni O, Goyal V (2018) Piecewise static policies for two-stage adjustable robust linear optimization. Math. Programming 169(2):649–665.Crossref, Google Scholar
• El Housni O, Goyal V (2021) On the optimality of affine policies for budgeted uncertainty sets. Math. Oper. Res. 46(2):674–711.Link, Google Scholar
• Garstka SJ, Wets RJ-B (1974) On decision rules in stochastic programming. Math. Programming 7(1):117–143.Crossref, Google Scholar
• Georghiou A, Tsoukalas A, Wiesemann W (2019) Robust dual dynamic programming. Oper. Res. 67(3):813–830.Link, 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
• Georghiou A, Wiesemann W, Kuhn D (2015) Generalized decision rule approximations for stochastic programming via liftings. Math. Programming 152(1):301–338.Crossref, Google Scholar
• Goh J, Sim M (2010) Distributionally robust optimization and its tractable approximations. Oper. Res. 58(4):902–917.Link, Google Scholar
• Gorissen BL, den Hertog D (2013) Robust counterparts of inequalities containing sums of maxima of linear functions. Eur. J. Oper. Res. 227(1):30–43.Crossref, Google Scholar
• Gounaris CE, Wiesemann W, Floudas CA (2013) The robust capacitated vehicle routing problem under demand uncertainty. Oper. Res. 61(3):677–693.Link, Google Scholar
• Guslitser E (2002) Uncertainty-immunized solutions in linear programming. Unpublished master’s thesis, Technion Israel Institute of Technology, Haifa.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) K-adaptability in two-stage distributionally robust binary programming. Oper. Res. Lett. 44(1):6–11.Crossref, Google Scholar
• Iancu D, Sharma M, Sviridenko M (2013) Supermodularity and affine policies in dynamic robust optimization. Oper. Res. 61(4):941–956.Link, Google Scholar
• Jiang R, Zhang M, Li G, Guan Y (2014) Two-stage network constrained robust unit commitment problem. Eur. J. Oper. Res. 234(3):751–762.Crossref, Google Scholar
• Kuhn D, Wiesemann W, Georghiou A (2011) Primal and dual linear decision rules in stochastic and robust optimization. Math. Programming 130(1):177–209.Crossref, Google Scholar
• Lamothe J, Hadj-Hamou K, Aldanondo M (2006) An optimization model for selecting a product family and designing its supply chain. Eur. J. Oper. Res. 169(3):1030–1047.Crossref, Google Scholar
• Mattia S, Poss M (2018) A comparison of different routing schemes for the robust network loading problem: Polyhedral results and computation. Comput. Optim. Appl. 69(3):753–800.Crossref, Google Scholar
• Minoux M (2010) Robust network optimization under polyhedral demand uncertainty is NP-hard. Discrete Appl. Math. 158(5):597–603.Crossref, Google Scholar
• Mohajerin Esfahani P, Kuhn D (2018) Data-driven distributionally robust optimization using the Wasserstein metric: Performance guarantees and tractable reformulations. Math. Programming 171(1–2):1–52.Crossref, Google Scholar
• Mutapcic A, Boyd S (2009) Cutting-set methods for robust convex optimization with pessimizing oracles. Optim. Methods Software 24(3):381–406.Crossref, Google Scholar
• Ordóñez F, Zhao J (2007) Robust capacity expansion of network flows. Networks 50(2):136–145.Crossref, Google Scholar
• Poss M (2014) A comparison of routing sets for robust network design. Optim. Lett. 8(5):1619–1635.Crossref, Google Scholar
• Poss M, Raack C (2013) Affine recourse for the robust network design problem: Between static and dynamic routing. Networks 61(2):180–198.Crossref, Google Scholar
• Postek KS, den Hertog D (2016) Multi-stage adjustable robust mixed-integer optimization via iterative splitting of the uncertainty set. INFORMS J. Comput. 28(3):553–574.Link, Google Scholar
• Shapiro A (2017) Interchangeability principle and dynamic equations in risk averse stochastic programming. Oper. Res. Lett. 45(4):377–381.Crossref, Google Scholar
• Shapiro A, Dentcheva D, Ruszczynski A, eds. (2009) Lectures on Stochastic Programming: Modeling and Theory, 2nd ed. (MPS-SIAM, Philadelphia).Crossref, Google Scholar
• Simchi-Levi D, Trichakis N, Zhang PY (2019) Designing response supply chain against bioattacks. Oper. Res. 67(5):1246–1268.Link, Google Scholar
• Skaf J, Boyd SP (2010) Design of affine controllers via convex optimization. IEEE Trans. Automatic Control 55(11):2476–2487.Crossref, Google Scholar
• Subramanyam A, Gounaris CE, Wiesemann W (2020) K-adaptability in two-stage mixed-integer robust optimization. Math. Programming Comput. 12(2):193–224.Crossref, Google Scholar
• Thiele A, Terry T, Epelman M (2010) Robust linear optimization with recourse. Technical report, Lehigh University and University of Michigan, Ann Arbor, MI.Google Scholar
• Wiesemann W, Kuhn D, Sim M (2014) Distributionally robust convex optimization. Oper. Res. 62(6):1358–1376.Link, 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–561.Crossref, Google Scholar
• Zhao C, Wang J, Watson J-P, Guan Y (2013) Multi-stage robust unit commitment considering wind and demand response uncertainties. IEEE Trans. Power Systems 28(3):2708–2717.Crossref, Google Scholar
• Zhen J, den Hertog D, Sim M (2018) Adjustable robust optimization via Fourier-Motzkin elimination. Oper. Res. 66(4):1086–1100.Link, Google Scholar