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:

${\begin{aligned}{\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{aligned}}$

The uncertain parameter is $d$, and the uncertainty set is the closed interval from $50$ to $100$. The first stage decision is for $n_{1}$ and $cost$; the second stage decision is $n_{2}$. Rewriting $n_{2}$ as a function of $d$ and rearranging into matrix form:

${\text{min}}(n_{1},cost,n_{2}(d))\;cost$

${\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 $n_{2}(d)=w+Wd$, noting that $w$ and $W$ are $1\times 1$ matrices, gives:

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

${\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:

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

${\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. A famous theorem of robust linear programming states that when the uncertainty set places only linear restrictions on the uncertain parameter, it suffices to consider only the extreme points of the uncertainty set [cite stanford notes? find a citation for this]. In this case, it suffices to check the constraint only for $d=50$ and $d=100$. Writing down the constraints for both values gives a deterministic linear program:

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

${\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 is $(n_{1},n_{2})=(150,0)$ for a total cost of $7000$. The solution corresponds to buying all 150 demand units for the two periods at start of the first period. This solution makes intuitive sense because the cost of buying at the start of the second period costs $\$15$ more, but storing any extra units from the first period costs only $\$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 actually found the optimal solution in this case. This is not surprising, since the optimal solution required $n_{2}$ to be zero in all cases, which is an affine function of the 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 [insert sources here].

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 $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 readers to [insert sources].

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 [insert reference].

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.