Adjustable robust optimization through multi-parametric programming
- PDF / 281,064 Bytes
- 15 Pages / 439.37 x 666.142 pts Page_size
- 37 Downloads / 210 Views
Adjustable robust optimization through multi-parametric programming Styliani Avraamidou1 · Efstratios N. Pistikopoulos1 Received: 28 February 2018 / Accepted: 21 May 2019 © Springer-Verlag GmbH Germany, part of Springer Nature 2019
Abstract Adjustable robust optimization (ARO) 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. Solving the general 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. In this work we propose a novel method for the derivation of generalized affine decision rules for linear mixedinteger ARO problems through multi-parametric programming, that lead to the exact and global solution of the ARO problem. The problem is treated as a multi-level programming problem and it is then solved using a novel algorithm for the exact and global solution of multi-level mixed-integer linear programming problems. 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. Keywords Adjustable robust optimization · Multi-parametric programming · Tri-level programming
1 Introduction Decisions taken in many disciplines have effects that can extend well into the future, therefore the outcome of such decisions are subject to uncertainties, such as variation in
B
Efstratios N. Pistikopoulos [email protected] Styliani Avraamidou [email protected]
1
Texas A&M Energy Institute, Texas A&M University, College Station, TX, USA
123
S. Avraamidou, E. N. Pistikopoulos
customer demands and changes in laws or technological advances. One of the dominant approaches to address decision making under uncertainty is robust optimization (RO). In RO, uncertainty is described by a distribution-free uncertainty set, typically a bounded convex set [6–8,10,14,15,20,21], and recourse decisions are not allowed, i.e. the decision maker makes all the decisions before the realization of the uncertainty, which can be overly conservative. Ben-Tal et al. [9] extended classical robust optimization to include adjustable decisions, with this class of problems being referred to as adjustable robust optimization (ARO) problems or two-stage robust optimization problems. A general form of a linear ARO problem is presented below (1). min c T x + max x
u∈U
min b T y
y∈Ω(x,u)
s.t. Ax ≥ d, x ∈ Sx Ω(x, u) = {y ∈ S y : W y ≥ h − T x − Mu}
(1)
where u is the uncertainty set, x are ‘here-and-now’ decis
Data Loading...
