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[ref Ben-Tal 2004]. 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[ref various papers].

Compared to traditional robust optimization models, ARO gives less conservative and more realistic solutions, however, this improvement comes at the cost of computation time[ref basically any paper]. Indeed, even the general linear ARO with linear uncertainty is proven computationally intractable[ref Ben-Tal 2004]. 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 [ref various papers].

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}$[ref various papers]. 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.

Algorithms and Methodology

General ARO problems are computationally intractable[ref basically any paper]. Taking the L2ARO for example, deriving the optimal function $x_{2}(u)$ poses a tremendous challenge for many choices of uncertainty set $U$. If $U$ is large or infinite, or is non convex, deciding what $x_{2}$ should be for each $u$ in $U$ may take a long time. In real world applications, then, the uncertainty set $U$ must be chosen carefully to include a representative set of possible parameter values for $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 $U$ or with restrictions imposed on the function $x_{2}(u)$[ref Ben-Tal 2004, other extensions of the work]. Therefore, ARO problems are usually solved on a case by case basis, using methods such as multi-level optimization, branch-and-cut, and decomposition[ref various papers]. 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 [ref], 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[ref Guslitser master's thesis]. Ben-Tal took this result and suggested simplifying the problem by restricting $x_{2}(u)$ to vary linearly with $u$, that is,

$x_{2}(u)=w+Wu$

Where $w$ is a vector and $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 $V$ (fixed recourse conditions), and make $A_{1}(u)$ and $b(u)$ affine functions of $u$:

$A_{1}(u)=m+M(u)$

$b(u)=b+Bu$

Where $m$ and $b$ are fixed vectors and $M$ and $B$ are fixed matrices. Then, the overall problem can be rewritten:

${\begin{aligned}{\text{min}}(x_{1},w,W)\;&c^{T}x_{1}\\{\text{s.t.}}\;&(m+Mu)x_{1}+V(w+Wu)\leq b+Bu\;{\text{ for all }}u{\text{ in }}U\end{aligned}}$

Now, both the objective function and constraint function are affine functions of $x_{1}$, $w$, and $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 $u$ is revealed. That is, if solving the L2ARO gives $x_{1}^{*}$ as the optimal $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, $u^{*}$), decision $x_{2}$ is decided not by computing $x_{2}^{*}(u^{*})$, but by re-solving the whole problem fixing $x_{1}$ to $x_{1}^{*}$ and fixing $u$ to $u^{*}$. This method reflects the wait-and-see nature of the decision $x_{2}$ - ADR is used to find a pretty-good $x_{1}$, then $u$ is revealed, then the information is used to solve for the optimal $x_{2}$ in that circumstance [ref that paper]. 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[ref that paper].

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 $u$, $x_{1}$ and $x_{2}$ are restricted to vectors with nonnegative entries, and $b(u)$ is restricted to be vectors with nonpositive entries, then ADRs are optimal if $b(u)$ is restricted to a polyhedral set with the same number of vertices as $b(u)$'s dimension[ref B+G 2012]. In a 2016 paper, Ben-Tal and colleagues noted that if the only restrictions were that the $A(u)$ matrices are independent of $u$, then piecewise ADRs can be optimal, although there may be a large number of pieces [ref Ben-Tal et al 2016]. ADRs can be optimal in other, more specific cases, but these cases will not be discussed here.

Still, ADRs are usually suboptimal. If the goal is to minimize the objective function, then the true optimal objective cannot exceed the optimal objective generated under ADRs, that is, applying ADRs actually gives an upper bound to the optimal solution. Thus, one approach to characterize the suboptimality of ADRs is to generate a lower bound to the optimal solution, and the difference between the upper and lower bounds can be used to estimate suboptimality. Several approaches exist for doing so. A simple approach is to approximate the uncertainty set using a small number of well-chosen points (“sampling” the uncertainty set), and to solve the model at each of these points. 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, suffers from being excessively optimistic unless a large number of points are sampled, but trying to solve the model at a large number of 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 optimality and computation time of this method. Other methods seek to extend duality theory to the L2ARO problem to find maximal lower bounds, to various degrees of complexity and optimality.

The other important assumption in the given solution methodology is the fixed recourse condition, that $A_{2}(u)$ is fixed to some matrix $V$. If this is not true, that $A_{2}(u)$ is instead some affine function of $u$, then even under the ADR assumption, the problem is intractable [ref Gusliter]. However, Ben-Tal has proposed a tight approximation method for when the uncertainty set $U$ is the intersection of ellipsoidal sets, an approximation that becomes exact if $U$ 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 that period. Let the storage cost of every unused unit of product be $\$10$ per business period. Let the unit price of the product be $\$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 $50$ and $100$ units.
2. The total demand over the two months is $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 $d$ (so the demand in the second period is $150-d$) and the quantity purchased in the $i$th period $n_{i}$, then we can formulate this as an L2ARO as follows: