(280a) Mixed-Integer Adjustable Robust Optimization through Multi-Parametric Programming

Classical robust optimization (RO) is an approach for incorporating uncertainty in optimization problems and traditionally assumes that all decisions must be made before the realization of uncertainty (referred to as “here-and-now” decisions), a strategy that may be overly conservative [1]. A less conservative approach is adjustable robust optimization (ARO) which involves recourse decisions (i.e. reactive actions after the realization of the uncertainty, “wait-and-see”) as functions of the uncertainty [2]. Solving ARO problems is challenging, therefore 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 [2, 3]; an approximation which can be overly conservative for general ARO problems.

In this work, we propose a novel method for the derivation of generalized affine decision rules for mixed-integer linear ARO problems under exogenous uncertainty through multi-parametric programming, which leads to the exact and global solution of the ARO problem. The proposed approach is based on our previous work on the solution of mixed-integer linear ARO problems under endogenous uncertainty [4]. The problem is treated as a multi-level programming problem [5] and it is then solved using B-POP, a novel algorithm and toolbox for the exact and global solution of multi-level mixed-integer linear or quadratic programming problems [6, 7, 8]. The main idea behind the proposed approach is to solve the lower optimization level of the ARO problem parametrically at the extrema realizations of the uncertainty, by considering “here-and-now” variables as parameters. This will result in a set of affine decision rules for the “wait-and-see” variables as a function of “here-and-now” variables, that are optimal for their entire feasible space. Several numerical problems are solved to illustrate the computational performance of the developed algorithm. Additionally, a case study on the robust solution of a plant design and operation problem is considered, where the design related decisions are treated as “here-and-now” variables, the operation or scheduling decisions are treated as “wait-and-see” variables, while price and demand fluctuations are considered as uncertainties.

[1] Ben-Tal, A., Ghaoui, L., Nemirovski, A. Robust optimization (2009) Princeton University Press, Princeton and Oxford.

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

[3] Kuhn, D., Wiesemann, W., Georghiou, A. Primal and dual linear decision rules in stochastic and robust optimization (2011) Mathematical Programming, 130 (1), pp. 177-209.

[4] Avraamidou, S.; Pistikopoulos, E. N. (2020) Adjustable Robust Optimization through multi-parametric programming. Optimization Letters, Available Online.

[5] Ning, C. and You, F. (2017) Data‐driven adaptive nested robust optimization: General modeling framework and efficient computational algorithm for decision making under uncertainty. AIChE J, 63, pp. 3790-3817.

[6] Avraamidou, S.; Pistikopoulos, E. N. (2019) B-POP: Bi-level Parametric Optimization Toolbox. Computers & Chemical Engineering, 122, pp. 193-202.

[7] Avraamidou, S.; Pistikopoulos, E. N. (2019) A Multi-Parametric optimization approach for bilevel mixed-integer linear and quadratic programming problems. Computers & Chemical Engineering, 125, pp.98-113.

[8] 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), pp. 443-465.