(365b) Mixed-Integer Adjustable Robust Optimization Under Exogenous Uncertainty

Adjustable robust optimization (ARO) is a class of optimization problems that involves uncertainties and considers both “here-and-now” decisions (i.e. decisions to be taken before uncertainties are revealed) and “wait-and-see” decisions (i.e. decisions to be taken after uncertainties are revealed) [1]. ARO can be applied to several types of control and scheduling optimization problems as a less conservative formulation than the classical robust optimization formulation, although finding the exact and global solution of mixed-integer ARO problems is very challenging due to the computational complexity of the problem [2]. Ways to reduce the computational effort have been proposed, with the most popular being the affine decision rules, where “wait-and-see” decisions are approximated as affine adjustments of the uncertainty [3]; an approximation which can be overly conservative for general ARO problems.

In this work, we propose a novel algorithm for solving mixed-integer linear and quadratic ARO problems under exogenous uncertainty (i.e. uncertainty that does not depend on “here-and-now” decisions) to global optimality. Building on our previous work on the solution of linear ARO problems under endogenous uncertainty [4], the proposed approach reformulates the ARO problem as a tri-level optimization problem, with the uncertainty optimization sub-problem treated as the leader or first level optimization problem. The resulting tri-level problem is then solved using our previously developed mixed-integer tri-level optimization solvers [5]. Several numerical examples are used to test the performance of our proposed algorithm. In addition, typical approaches such as the column-and-constraint generation algorithm [6] and the classical affine decision rules [3] are used for benchmarking, comparing both the computational efficiency and quality of solution for ARO problems with varying dimensionalities.

References:

[1] Ben-Tal, A., El Ghaoui, L., & Nemirovski, A. (2009). Robust optimization. In Robust optimization. Princeton university press.

[2] Pappas, I., Kenefake, D., Burnak, B., Avraamidou, S., Ganesh, H. S., Katz, J., ... & Pistikopoulos, E. N. (2021). Multiparametric programming in process systems engineering: Recent developments and path forward. Frontiers in Chemical Engineering, 32.

[3] Ben-Tal, A., Goryashko, A., Guslitzer, E., & Nemirovski, A. (2004). Adjustable robust solutions of uncertain linear programs. Mathematical programming, 99(2), 351-376.

[4] Avraamidou, S., & Pistikopoulos, E. N. (2020). Adjustable robust optimization through multi-parametric programming. Optimization Letters, 14(4), 873-887.

[5] Avraamidou, S. & Pistikopoulos, E. N. (2019) Multi-parametric global optimization approach for tri-level mixed-integer linear optimization problems. Journal of Global Optimization 74(3), 443-465.

[6] Zeng, B., & Zhao, L. (2013). Solving two-stage robust optimization problems using a column-and-constraint generation method. Operations Research Letters, 41(5), 457-461.