Adaptive robust optimization

Author: Ralph Wang (ChemE 6800 Fall 2020)

Steward: Allen Yang, Fengqi You

Introduction

Adaptive Robust Optimization (ARO), also known as adjustable robust optimization, models situations where decision makers make two types of decisions: here-and-now decisions that must be made immediately, and wait-and-see decisions that can be made at some point in the future. ARO improves on the robust optimization framework by accounting for any information the decision maker does not know now, but may learn before making future decisions. In the real-world, ARO is applicable whenever past decisions and new information together influence future decisions. Common applications include power systems control, inventory management, shift scheduling, and other resource allocation problems.

Compared to traditional robust optimization models, ARO gives less conservative and more realistic solutions, however, this improvement comes at the cost of computation time. Indeed, even the general linear ARO with linear uncertainty is proven computationally intractable. However, researchers have developed a wide variety of solution and approximation methods for specific industrial ARO problems over the past 15 years and the field continues to grow rapidly.

Problem Formulation

Suppose, for an optimization problem of interest, $S$ is the set of allowed decisions and $x$ is a decision in $S$. Let $u$ bee a vector representing the set of parameters of interest in this problem. If the goal is to minimize some function $f(u,x)$, and we want $x$ to adhere to a set of constraints $g(u,x)\leq 0$, then the problem may be formulated as:

${\begin{aligned}{\text{minimize, choosing x: }}f&(u,x)\\{\text{under constraints: }}g&(u,x)\leq 0\end{aligned}}$

Or more simply:

${\begin{aligned}{\text{min}}(x)\;&f(u,x)\\{\text{s.t. }}\;&g(u,x)\leq 0\end{aligned}}$

In this formulation, we call $f$ the objective function and $g$ the constraint function. If $u$ is known, then the problem can be solved using methods such as branch and cut or KKT conditions. However, in many real world scenarios, $u$ is not known. To address this uncertainty, the robust optimization approach generates the set of possible values of $u$, called the uncertainty set $U$, and solves for the decision $x$ such that the constraint $g$ is satisfied in all cases and $f$ is optimized for the worst case. The problem can be written as:

${\begin{aligned}{\text{min}}(x){\text{ max}}(u)\;&f(u,x)\\{\text{s.t.}}\;&g(u,x)\leq 0\end{aligned}}$

Adaptive robust optimization expands this robust optimization framework by separating the decision $x$ into multiple stages. For simplicity, assume there are two stages of decisions: in the first stage, only a subset of the decisions are made. After these decisions are made, the true values of the parameters $u$ are revealed, then the remaining set of decisions need to be made. The model is like a game of poker: the player needs to make initial bets based on incomplete information (the cards in his hand), then makes further bets as more and more cards are dealt. Mathematically, let the set of possible decisions in the first stage be $S_{1}$ and the set of possible decisions in the second stage be $S_{2}$, so that the objective and constraint functions become functions of the parameters $u$, the first stage decision $x_{1}$ ($x_{1}inS_{1}$), and the second stage decision $x_{2}$ ($x_{2}$ in $S_{2}$). Then, we can formulate the problem as:

${\begin{aligned}{\text{min}}(x_{1}){\text{ max}}(u){\text{ min}}(x_{2})\;&f(u,x_{1},x_{2})\\{\text{s.t.}}\;\;\;&g(u,x_{1},x_{2})\leq 0\;{\text{for all }}u{\text{ in }}U\end{aligned}}$

The reasoning used in this construction can be extended to multi-stage formulations.

In the literature, adaptive robust optimization problems are usually formulated differently but equivalently. Note that because $x_{2}$ is selected only after the uncertain parameter $u$ is revealed, $x_{2}$ is a function of $u$. Then, the function $x_{2}(u)$ is independent of $u$, so the function can be decided before $u$ is revealed. This allows us to rewrite the problem as:

${\begin{aligned}{\text{min}}(x_{1},x_{2}(u)){\text{ max}}(u)\;&f(u,x_{1},x_{2}(u))\\{\text{s.t.}}\;&g(u,x_{1},x_{2}(u))\leq 0\;{\text{for all }}u{\text{ in }}U\end{aligned}}$

And if we introduce a variable $t={\text{max}}(u)\;f(u,x_{1},x_{2}(u))$, then we can rewrite the problem as:

${\begin{aligned}{\text{min}}(x_{1},x_{2}(u),t)\;\;&t\\{\text{s.t.}}\;&f(u,x_{1},x_{2}(u))\leq t{\text{ for all }}u{\text{ in }}U\\&g(u,x_{1},x_{2}(u))\leq 0{\text{ for all }}u{\text{ in }}U\end{aligned}}$

Which allows us to remove $u$ from the objective function. Since $x_{1}$ represents all the variables the decide immediately, $t$ can be collapsed into $x_{1}$; similarly, the first constraint can be collapsed into the second. This generates the formulation most commonly seen in the literature (up to a change of variable names and functions $f$ and $g$):

${\begin{aligned}{\text{min}}(x_{1},x_{2}(u))\;&f(x_{1})\\{\text{s.t.}}\;&g(u,x_{1},x_{2}(u))\leq 0{\text{ for all }}u{\text{ in }}U\end{aligned}}$

Where $f(x_{1})$ was redefined to be the part of $x_{1}$ representing $t$.

For many problems of interest, the functions $f$ and $g$ vary linearly with $x_{1}$ and $x_{2}$, that is, they are affine functions of $x_{1}$ and $x_{2}$. In such cases, if $x_{1}$ and $x_{2}$ are treated as vectors, then we can write:

$f(x_{1})=c^{T}x_{1}$

Where $c$ is some vector, and

$g(u,x_{1},x_{2})=A_{1}(u)x_{1}+A_{2}(u)x_{2}(u)-b(u)$

Where the $A(u)$'s are matrices and $b(u)$ is a vector, to give the linear, two-stage ARO (L2ARO):

${\begin{aligned}{\text{min}}(x_{1},x_{2}(u))\;&c^{T}x_{1}\\{\text{s.t.}}\;&A_{1}(u)x_{1}+A_{2}(u)x_{2}(u)\leq b(u)\;{\text{ for all }}u{\text{ in }}U\end{aligned}}$

This L2ARO will be the primary focus of the Algorithms section.