(461d) Derivation of Generalized Affine Decision Rules for Mixed Integer Linear, Quadratic and Nonlinear Adjustable Robust Optimization Problems By 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 which may be overly conservative (1). A more realistic 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, typically posed in a two-stage stochastic setting (2). Solving the general ARO problems is very difficult, 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 is exact and optimal only for the case of linear ARO problems.

In this work we propose a novel method for the derivation of generalized affine decision rules for linear/quadratic/nonlinear and mixed-integer ARO problems through multi-parametric programming. The ARO problem is treated as a multi-level programming problem (4) and it is then solved using M-POP, which is a novel algorithm for the exact and global solution of multi-level mixed-integer linear or quadratic programming problems (5, 6). The main idea behind the proposed approach is to solve the lower optimization level of the ARO problem parametrically, by considering “here-and-now” variables and uncertainties 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 and uncertainties for their entire feasible space. A set of illustrative numerical examples are provided to demonstrate the potential of the proposed novel approach.

References:

(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) Ning, C., You, F. Data-driven adaptive nested robust optimization: General modeling framework and efficient computational algorithm for decision making under uncertainty (2017) AIChE Journal; In Press (onlinelibrary.wiley.com/doi/10.1002/aic.15717/pdf)

(5) Faisca, N.P., Dua, V., Rustem, B., Saraiva, P.M., Pistikopoulos, E.N. Parametric global optimisation for bilevel programming (2007) Journal of Global Optimization, 38 (4), pp. 609-623.

(6) Avraamidou, S., Diangelakis, N. A., Pistikopoulos, E. N. Mixed Integer Bilevel Optimization through Multi-parametric Programming (2017) Foundations of Computer Aided Process Operations / Chemical Process Control; In Press. (http://folk.ntnu.no/skoge/prost/proceedings/focapo-cpc-2017/FOCAPO-CPC%2...)