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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align}\text{min}(x_1)\text{ max}(u)\text{ 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{align}}