Adaptive robust optimization

Author: Ralph Wang (ChemE 6800 Fall 2020)

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 types of industrial ARO problems over the past 15 years and the field continues to grow rapidly.

Problem Formulation

Suppose, for an optimization problem of interest, 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 S} is the set of allowed decisions 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 x} is a decision in 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 S} . Let 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 u} be a vector representing the set of parameters of interest in this problem. If the goal is to minimize some function 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 f(u, x)} , and we want $x$ to adhere to a set of constraints 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(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 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 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 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 u} is known, then the problem can be solved using methods such as branch and cut or Karush-Kuhn-Tucker conditions. However, in many real world scenarios, 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 u} is not known. To address this uncertainty, the robust optimization approach generates the set of possible values of 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 u} , called the uncertainty set 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 U} , and solves for the decision 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 x} such that the constraint 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} is satisfied in all cases 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 f} is optimized for the worst case. The problem can be written 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)\text{ max}(u)\;&f(u, x)\\ \text{s.t.}\;&g(u, x) \leq 0 \end{align}}

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 the urgent, here-and-now decisions are made. After these decisions are made, the true values of the parameters 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 u} are revealed, then the remaining, wait-and-see decisions are decided. 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 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 S_1} and the set of possible decisions in the second stage be 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 S_2} , so that the objective and constraint functions become functions of the parameters 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 u} , the first stage decision 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 x_1} (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 x_1} in 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 S_1} ), and the second stage decision 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 x_2} (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 x_2} in 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 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{ 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{align}}

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 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 x_2} is selected only after the uncertain parameter 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 u} is revealed, 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 x_2} is a function of 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 u} . Expressing 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 x_2} as a function of 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 u} allows us to choose the function 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 x_2(u)} before learning 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 u} , which allows the problem to be rewritten 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, 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{align}}

And if we introduce a variable $t={\text{max}}(u)\;f(u,x_{1},x_{2}(u))$, then we can rewrite 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, 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{align}}

Which allows us to remove 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 u} from the objective function. Since 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 x_1} represents all the variables the decide immediately, 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 t} can be collapsed into 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 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 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 f} 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} ):

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, 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{align}}

Where 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 f(x_1)} was redefined to be the part of $x_{1}$ representing 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 t} .

For many problems of interest, the functions 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 f} 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} vary linearly with 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 x_1} 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 x_2} , that is, they are affine functions of 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 x_1} 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 x_2} . In such cases, if 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 x_1} 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 x_2} are treated as vectors, then we can write:

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

Where 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 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.

Algorithms and Methodology

General ARO problems are computationally intractable. Taking the L2ARO for example, deriving the optimal function 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 x_2(u)} poses a tremendous challenge for many choices of uncertainty set 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 U} . If 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 U} is large or infinite, or is non convex, deciding what 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 x_2} should be for each 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 u} in 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 U} may take a long time. In real world applications, then, the uncertainty set 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 U} must be chosen carefully to include a representative set of possible parameter values for 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 u} , but it must not be too large or complex and render the problem intractable. The L2ARO model has been proven tractable only for simple uncertainty sets 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 U} or with restrictions imposed on the function 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 x_2(u)} . Therefore, ARO problems are usually solved on a case by case basis, using methods such as multi-level optimization, branch-and-cut, and decomposition. This section will first present the L2ARO solution method using the affine decision rule approximation under fixed recourse conditions from Ben-Tal's 2004 paper, then discuss how this method might be extended to other L2ARO problems.

General L2ARO problems were first proven intractable by Guslitser, in his master's thesis. Ben-Tal took this result and suggested simplifying the problem by restricting 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 x_2(u)} to vary linearly with 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 u} , that is,

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 x_2(u) = w + Wu}

Where 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 w} is a vector 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 W} is a matrix, both variable. This simplification is known as the affine decision rule (ADR). To further simplify the problem, Ben-Tal proposed that the matrix $A_{2}(u)$ be fixed to some matrix 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 V} (fixed recourse conditions), and make 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 A_1(u)} 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 b(u)} affine functions of 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 u} :

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 A_1(u) = m + M(u)}

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 b(u) = b + Bu}

Where $m$ and $b$ are fixed vectors and $M$ 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 B} are fixed matrices. Then, the overall problem can be rewritten:

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, w, W) \; &c^Tx_1\\ \text{s.t.}\;&(m + Mu)x_1 + V(w + Wu) \leq b + Bu \; \text{ for all }u\text{ in }U\end{align}}

Now, both the objective function and constraint function are affine functions of 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 x_1} , 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 w} , 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 W} , so the problem has been reduced to a simple robust linear program, for which solution methods already exist.

The above solution method, although simple and tractable, suffers from potential sub optimality of ADR. Indeed, Ben-Tal motivates this assumption citing only the tractability of the result. In real world scenarios, this sub optimality can be mitigated by using ADR to make the initial decision, then resolving the problem after 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 u} is revealed. That is, if solving the L2ARO gives 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 x_1^*} as the optimal 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 x_1} and $x_{2}^{*}(u)$ as the optimal $x_{2}(u)$, decision $x_{1}^{*}$ is implemented immediately; when $u$ is revealed (to be, say, 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 u^*} ), decision $x_{2}$ is decided not by computing 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 x_2^*(u^*)} , but by re-solving the whole problem fixing 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 x_1} to $x_{1}^{*}$ and fixing 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 u} to $u^{*}$. This method reflects the wait-and-see nature of the decision $x_{2}$ - ADR is used to find a pretty-good 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 x_1} , then $u$ is revealed, then the information is used to solve for the optimal 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 x_2} in that circumstance. This iterative, stage-by-stage solution performs better than using only ADR, but is feasible only when there is enough time between stages to re-solve the problem. Further, numerical experiments indicate that classical robust optimization models yield equally good, if not better initial decisions than ADR on L2ARO, limiting ADR on L2ARO to situations where the problem cannot be feasibly re-solved, or in the special cases where the ADR approximation actually generates the optimal solution.

This leads to the natural question, under what conditions are ADRs optimal? Bertsimias and Goyal showed in 2012 that if both $A(u)$ matrices are independent of 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 u} , 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 x_1} 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 x_2} are restricted to vectors with nonnegative entries, 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 b(u)} is restricted to be vectors with nonpositive entries, then ADRs are optimal if 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 b(u)} is restricted to a polyhedral set with a number of vertices one more than 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 b(u)} 's dimension. In a 2016 paper, Ben-Tal and colleagues noted that whenever the 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 A(u)} matrices are independent of 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 u} , then a piecewise ADR can be optimal, albeit one with a large number of pieces. ADRs can be optimal in other, more specific cases, but these cases will not be discussed here.

In most cases, however, ADRs are suboptimal, and it becomes useful to characterize its degree of suboptimality. The most common approach is to generate upper and lower bounds on the optimal value of the objective function. If the goal is to minimize the objective function, then any valid solution (via ADRs or some other method) gives an upper bound, so the problem reduces to computing lower bounds. A simple approach to doing so is to approximate the uncertainty set using a small number of well-chosen points (“sampling” the uncertainty set), solve the model at each of these points, and find the worst case among these sampled solutions. Since the true worst case scenario must be at least as bad as one of the selected points, this sampling approach must generate a solution no worse than the true optimal, or a lower bound to the objective. This method, although simple, generates excessively optimistic lower bounds unless a large number of points are sampled, but solving the model at many such points can take a long time. Thus, authors have investigated methods for choosing fewer points that can better represent the whole uncertainty set to improve both the lower bound quality and computation time for this method. For example, Bertsimias and De Ruiter discovered that constructing the dual and sampling the dual uncertainty set gives better bounds and faster computation time.

The other important assumption in the given solution methodology is the fixed recourse condition, that 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 A_2(u)} is fixed to some matrix 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 V} . If this is not true, that 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 A_2(u)} is instead some affine function of 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 u} , then even under the ADR assumption, the problem is intractable. However, Ben-Tal has proposed a tight approximation method for cases where the uncertainty set 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 U} is the intersection of ellipsoidal sets, an approximation that becomes exact if 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 U} itself is an ellipsoidal set.

Numerical Example

Consider a simple inventory management problem over two business periods involving one product that loses all value at the end of the second period. Let the storage cost of every unused unit of product be 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 $10} per business period. Let the unit price of the product be 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 $40} be in the first business period and $\$55$ in the second period. Let the demand in each period be uncertain, but given the following information:

1. Both demands are between 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 50} 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 100} units.
2. The total demand over the two periods is 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 150} units.

The problem is that the manager must decide the quantity of each product to purchase at the start of each business period minimizing storage and purchasing costs. If we denote the demand in the first business period 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 d} (so the demand in the second period is 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 150 - d} ) and the quantity purchased in the 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 i} th period 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 n_i} , then we can formulate this as an L2ARO as follows:

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} \; &cost\\ \text{s.t.} \; &cost \geq 10(n_1-d) + 10(n_1+n_2-150) + 40n_1 + 55n_2 \;\text{ for all }d\\ &n_1 - d \geq 0 \;\text{ for all }d\\ &n_1 + n_2 \geq 150\\ &n_1 \geq 0\\ &n_2 \geq 0\\ &50 \leq d \leq 100 \end{align}}

The uncertain parameter is $d$, and the uncertainty set is the closed interval from 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 50} to 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 100} . The first stage decision is for 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 n_1} 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 cost} ; the second stage decision is 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 n_2} . Rewriting 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 n_2} as a function of 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 d} and rearranging into matrix form:

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 \text{min}(n_1, cost, n_2(d)) \; cost}

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 \text{s.t.}\;\begin{bmatrix} -60 & 1 \\ 1 & 0 \\ 1 & 0 \\ 1 & 0 \\ 0 & 1 \end{bmatrix}\begin{bmatrix}n_1 \\ cost\end{bmatrix} + \begin{bmatrix} -65 \\ 0 \\ 1 \\ 0 \\ 1\end{bmatrix}n_2(u) \geq \begin{bmatrix} -1500 \\ 0 \\ 150 \\ 0 \\ 0\end{bmatrix} + \begin{bmatrix} -10 \\ 1 \\ 0 \\ 0 \\ 0\end{bmatrix}d\;\text{ for all }d }

Applying the affine decision rule 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 n_2(d) = w + Wd} , noting that $w$ 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 W} are 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 1\times1} matrices, gives:

${\text{min}}(n_{1},cost,w,W)\;cost$

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 \text{s.t.}\;\begin{bmatrix} -60 & 1 \\ 1 & 0 \\ 1 & 0 \\ 1 & 0 \\ 0 & 1 \end{bmatrix}\begin{bmatrix}n_1 \\ cost\end{bmatrix} + \begin{bmatrix} -65 \\ 0 \\ 1 \\ 0 \\ 1\end{bmatrix}(w + Wd) \geq \begin{bmatrix} -1500 \\ 0 \\ 150 \\ 0 \\ 0\end{bmatrix} + \begin{bmatrix} -10 \\ 1 \\ 0 \\ 0 \\ 0\end{bmatrix}d\;\text{ for all }d }

Which rearranges to:

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 \text{min}(n_1, cost, w, W) \; cost}

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 \text{s.t.}\; \begin{bmatrix} -60 & 1 & -65 & -65d \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & d \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & d\end{bmatrix} \begin{bmatrix}n_1 \\ cost \\ w \\ W\end{bmatrix} \geq \begin{bmatrix}-1500 \\ 0 \\ 150 \\ 0 \\ 0\end{bmatrix} + \begin{bmatrix}-10 \\ 1 \\ 0 \\ 0 \\ 0\end{bmatrix}d\; \text{ for all }d }

Which is a robust linear program. Since the constraints are linear inequalities in $d$ 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 d} is bounded between $50$ 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 100} , it suffices to check the constraint only for $d=50$ 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 d = 100} . Writing down the constraints for both values gives a deterministic linear program:

${\text{min}}(n_{1},cost,w,W)\;cost$

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 \text{s.t.}\; \begin{bmatrix} -60 & 1 & -65 & -3250 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 50 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 50 \\ -60 & 1 & -65 & -6500 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 100 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 100\end{bmatrix} \begin{bmatrix}n_1 \\ cost \\ w \\ W\end{bmatrix} \geq \begin{bmatrix}-2000 \\ 50 \\ 150 \\ 0 \\ 0 \\ -2500 \\ 100 \\ 150 \\ 0 \\ 0\end{bmatrix} }

Which can be solved using the Simplex Algorithm. The solution to this linear program is $(n_{1},cost,w,W)=(150,7000,0,0)$, corresponding to a worst-case cost of $7000$. The solution corresponds to buying all 150 demand units for the two periods at start of the first period, but only having a demand of 50 units in the first business period. This solution makes intuitive sense because the purchase price for the second period is $\$15$ more than for the first period, but storing any extra units from the first period costs 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 $10} , so in any case, the price increase outweighs the storage cost. This is indeed the optimal solution to the problem.

Note that the ADR approximation found the optimal solution. This is not surprising because the optimal strategy as described above does not depend on the first period demand.

Applications

Applications of adaptive robust optimization typically involve multi-stage allocation of resources under uncertain supply or demand, including problems in energy systems, inventory management, and shift scheduling..

Energy Systems

Energy systems aim to meet energy demand while minimizing costs. An energy system may involve multiple units that can each be turned on or off, with corresponding startup, shut down, and operation costs. A coal plant may be expensive to start up and shut down, but be cheap to operate, for example, while a solar farm may be easier to start up and shut down but more difficult to maintain. Let each day be partitioned into $n$ different blocks of time, and suppose the problem was to determine the optimal combination of units to run during each time block on a given day. The unit combination for the first block of time must be decided immediately, but decisions for the subsequent time blocks can wait until after learning the energy demand in preceding time blocks. However, past decisions influence future decisions - starting up the coal plant in the first time block allows it to produce cheap energy all day, potentially reducing a reliance on other energy sources. Such a decision structure, where past decisions and new information guide future decisions, lends itself naturally to an ARO model. The decision is the combination of units to run in each time block, the uncertainty set $U$ is the set of possible energy demands for each time block, the constraint is that the power produced meets demand for each time block, and the objective would be to minimize the total startup, shut down, and operation costs for the day. For more detailed treatments of ARO applied to energy systems, we refer the reader to the references.

Inventory Management

The inventory management problem seeks to purchase goods at regular intervals and store them such that there’s always enough product on hand to satisfy demand while minimizing purchase and storage costs. Purchasing large amounts when the prices are low saves on purchasing costs later on, but this incurs large storage costs. On the other extreme, keeping too little inventory risks running out of stock or requiring large purchases at inconvenient times. If an inventory planner wanted to plan purchases for the next $n$ time blocks (for simplicity assuming purchases take place only at the start of each time block), then he must immediately decide how much to purchase for the first time block, then use each past time block’s prices and demands to decide how much to buy at future time blocks. As in the case of energy systems, the inventory management problem has a staggered decision structure where past decisions and new information inform future decisions, and can be translated naturally into an ARO model. The decisions are the quantities of product to purchase at the start of each time block, the uncertainty set is the set of possible prices and demands for each of the 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 n} time blocks, the constraint is that the inventory has enough stock to meet demand in every time block, and the objective is to minimize purchasing and storage costs. For more detailed analyses of the inventory management problem, we refer again readers to the references.

Shift Scheduling

The shift scheduling problem involves carefully choosing a shift for each employee such that the operation center has enough staff at all times. For example, a customer service line would ideally like to predict the frequency and length of calls at every hour of the day so it employs exactly enough operators to handle the calls, however, call volume is hard to predict and call centers often end up overstaffed or understaffed, so that the company may spend excess on paying workers or deliver unsatisfactory customer service. However, Mattia and colleagues note that consecutive periods of high volume calls are not independent, so that past call volumes help predict future call volumes, so they formulated the shift scheduling problem as a two-stage ARO. In the first stage (over the weekend), employees shifts are laid out for the workweek; in the second stage (during the week), employees are allocated to different jobs in the office. The uncertainty set is the set of possible call volume distributions through the week (represented as the deviations in the number of staff for handling all other jobs), the constraint is that enough staff is present to handle the various office jobs, and the objective is to minimize the total cost of hiring the employees for the hours they work. For more detail on this problem, we refer readers to the paper by Mattia and colleagues.

Conclusion

Adaptive robust optimization models multi-stage decision making where past decisions affect future decision making, but new information is learned between decision stages. It finds less conservative solutions than traditional robust optimization without sacrificing robustness, at the expense of simplicity and computation time. Many ARO problems are computationally intractable, but ARO problems have also been solved for many specific problems in the field, and will continue to grow in the coming decades.