Pareto Adaptive Robust Optimality via a Fourier–Motzkin Elimination lens
Springer Science and Business Media LLC - Trang 1-54 - 2023
Tóm tắt
We formalize the concept of Pareto Adaptive Robust Optimality (PARO) for linear two-stage Adaptive Robust Optimization (ARO) problems, with fixed continuous recourse. A worst-case optimal solution pair of here-and-now decisions and wait-and-see decisions is PARO if it cannot be Pareto dominated by another solution, i.e., there does not exist another worst-case optimal pair that performs at least as good in all scenarios in the uncertainty set and strictly better in at least one scenario. We argue that, unlike PARO, extant solution approaches—including those that adopt Pareto Robust Optimality from static robust optimization—could fail in ARO and yield solutions that can be Pareto dominated. The latter could lead to inefficiencies and suboptimal performance in practice. We prove the existence of PARO solutions, and present approaches for finding and approximating such solutions. Amongst others, we present a constraint & column generation method that produces a PARO solution for the considered two-stage ARO problems by iteratively improving upon a worst-case optimal solution. We present numerical results for a facility location problem that demonstrate the practical value of PARO solutions. Our analysis of PARO relies on an application of Fourier–Motzkin Elimination as a proof technique. We demonstrate how this technique can be valuable in the analysis of ARO problems, besides PARO. In particular, we employ it to devise more concise and more insightful proofs of known results on (worst-case) optimality of decision rule structures.
Tài liệu tham khảo
Bemporad, A., Borrelli, F., Morari, M.: Min–max control of constrained uncertain discrete-time linear systems. IEEE Trans. Autom. Control 48(9), 1600–1606 (2003)
Ben-Tal, A., Goryashko, A., Guslitzer, E., Nemirovski, A.: Adjustable robust solutions of uncertain linear programs. Math. Program. 99, 351–376 (2004)
Ben-Tal, A., El Ghaoui, L., Nemirovski, A.: Robust Optimization. Princeton University Press, Princeton Series in Applied Mathematics, Princeton (2009)
Ben-Tal, A., El Housni, O., Goyal, V.: A tractable approach for designing piecewise affine policies in two-stage adjustable robust optimization. Math. Program. 182, 57–102 (2020)
Bertsimas, D., Goyal, V.: On the power and limitations of affine policies in two-stage adaptive optimization. Math. Program. 134, 491–531 (2012)
Bertsimas, D., Tsitsiklis, J.N.: Introduction to Linear Optimization. Athena Scientific, Nashua (1997)
Bertsimas, D., Brown, D.B., Caramanis, C.: Theory and applications of robust optimization. SIAM Rev. 53(3), 464–501 (2011)
Bertsimas, D., Bidkhori, H., Dunning, I.: The price of flexibility, unpublished manuscript (2019)
De Ruiter, F.J.C.T., Brekelmans, R.C.M., den Hertog, D.: The impact of the existence of multiple adjustable robust solutions. Math. Program. 160, 531–545 (2016)
Fourier, J.: Reported in: Analyse des travaux de l’Académie, Royale des Sciences, pendant l’année 1824, Partie mathématique. In: Mémoires de l’Académie des sciences de l’Institut de France, vol 7, Académie des sciences (1827)
Gabrel, V., Murat, C., Thiele, A.: Recent advances in robust optimization: an overview. Eur. J. Oper. Res. 235, 471–483 (2014)
Gorissen, B.L., Yanıkoğlu, I., den Hertog, D.: A practical guide to robust optimization. Omega 53, 124–137 (2015)
Gurobi Optimization LLC: Gurobi optimizer reference manual. http://www.gurobi.com (2020)
Guslitser, E.: Uncertainty-immunized solutions in linear programming. Master’s thesis, Technion - Israel Institute of Technology. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.623.2382 &rep=rep1 &type=pdf (2002)
Hadjiyiannis, M.J., Goulart, P.J., Kuhn, D.: A scenario approach for estimating the suboptimality of linear decision rules in two-stage robust optimization. In: 50th IEEE Conference on Decision and Control and European Control Conference, pp. 7386–7391 (2011)
Iancu, D.A., Trichakis, N.: Pareto efficiency in robust optimization. Manag. Sci. 60(1), 130–147 (2014)
Jabr, R.A.: Adjustable robust OPF with renewable energy sources. IEEE Trans. Power Syst. 28(4), 4742–4751 (2013)
Koçyiğit, Ç., Iyengar, G., Kuhn, D., Wiesemann, W.: Distributionally robust mechanism design. Manag. Sci. 66(1), 159–189 (2019)
Konno, H.: A cutting plane algorithm for solving bilinear programs. Math. Program. 11, 14–27 (1976)
Kuhn, D., Wiesemann, W., Georghiou, A.: Primal and dual linear decision rules in stochastic and robust optimization. Math. Program. 130, 177–209 (2009)
Marandi, A., den Hertog, D.: When are static and adjustable robust optimization problems with constraint-wise uncertainty equivalent? Math. Program. 170(2), 555–568 (2018)
Motzkin, T.: Beitráge zur Theorie der linearen Ungleichungen. Azriel, Jerusalem (1936)
Nahapetyan, A.H.: Bilinear programming. In: Floudas, C.A., Pardalos, P.M. (eds.) Encyclopedia of Optimization, pp. 279–288. Springer, Berlin (2009)
Polinder, G.J., Breugem, T., Dollevoet, T., Maróti, G.: An adjustable robust optimization approach for periodic timetabling. Transp. Res. B-Methodol. 128, 50–68 (2019)
Rockafellar, T.R.: Convex Analysis. Princeton University Press, Princeton (1970)
Ten Eikelder, S.C.M., Ajdari, A., Bortfeld, T., den Hertog, D.: Adjustable robust treatment-length optimization in radiation therapy. Optim. Eng. 23, 1949–1986 (2022)
Yanıkoğlu, I., Gorissen, B.L., den Hertog, D.: A survey of adjustable robust optimization. Eur. J. Oper. Res. 277, 799–813 (2019)
Zeng, B., Zhao, L.: Solving two-stage robust optimization problems using a column-and-constraint generation method. Oper. Res. Lett. 41(5), 457–461 (2013)
Zhen, J., den Hertog, D.: Computing the maximum volume inscribed ellipsoid of a polytopic projection. INFORMS J. Comput. 30(1), 31–42 (2018)
Zhen, J., den Hertog, D., Sim, M.: Adjustable robust optimization via Fourier–Motzkin elimination. Oper. Res. 66(4), 1086–1100 (2018)
Zhen, J., de Moor, D., den Hertog, D.: An extension of the Reformulation-Linearization Technique to nonlinear optimization. Optimization (2021)
Zhen, J., Marandi, A., de Moor, D., den Hertog, D., Vandenberghe, L.: Disjoint bilinear programming: a two-stage robust optimization perspective. INFORMS J. Comput. 34(5), 2410–2427 (2022)