A Practical Guide to Robust Optimization

Bram L. Gorissen; Ihsan Yanıkoğlu; Dick den Hertog

Source-linked AI summary

A Practical Guide to Robust Optimization

Bram L. Gorissen, Ihsan Yanıkoğlu, Dick den Hertog

arXiv:1501.02634v1Jan 12, 2015math.OC

TL;DR

Robust optimization is practically useful but underused because real-life applications lag behind its potential. This paper introduces RO and practical application guidance, reporting insights on tractable reformulations, adjustable decisions, uncertainty sets, and implementation trade-offs.

Problem
Robust optimization offers tractable, information-tailored formulations, yet real-life applications remain limited relative to their potential.
Method
The paper gives a concise RO introduction and practical procedure, covering adjustable RO, reformulations, uncertainty sets, and practitioner do’s and don’ts through examples.
Results
The paper reports practical insights including non-equivalent robust counterparts, possible advantages of re-optimization, and differences between actual and approximated probability guarantees.
Takeaways & Limitations
Practitioners can use the paper’s procedure and guidance to apply robust optimization in a more successful and convincing way.
Takeaways & Limitations
Adjustable robust counterparts can become intractable as the number of integer variables grows, creating a trade-off between optimality and computational complexity.

Abstract

from arXiv · show

Robust optimization is a young and active research field that has been mainly developed in the last 15 years. Robust optimization is very useful for practice, since it is tailored to the information at hand, and it leads to computationally tractable formulations. It is therefore remarkable that real-life applications of robust optimization are still lagging behind; there is much more potential for real-life applications than has been exploited hitherto. The aim of this paper is to help practitioners to understand robust optimization and to successfully apply it in practice. We provide a brief introduction to robust optimization, and also describe important do's and don'ts for using it in practice. We use many small examples to illustrate our discussions.

1 Introduction

Robust optimization addresses uncertain data without requiring known probability distributions, using uncertainty sets and hard constraints to obtain tractable formulations. This paper explains the framework and practical guidance for applying it.

Robust optimization models uncertain data through an uncertainty set rather than assuming known probability distributions.
Despite extensive applications and practical value, real-life use of robust optimization remains below its potential.
RO is useful in practice because it is tailored to available information and often produces computationally tractable formulations.
The paper introduces basic and adjustable RO, discusses practical do’s and don’ts, and uses small examples to support practitioners.
A central practical issue is specifying the user-defined uncertainty set that determines which uncertain parameter values are considered.

2 Introduction to robust optimization

This section introduces robust optimization through its modeling assumptions and shows how uncertain constraints can be converted into tractable robust counterparts. It also presents adversarial solution methods and adjustable decisions for settings where direct reformulation is difficult or decisions can adapt to observed data.

The basic formulation uses uncertain coefficients and a user-specified uncertainty set, while objective certainty, right-hand-side certainty, convex compact uncertainty, and constraint-wise uncertainty can be assumed without loss of generality in the stated setting.The constraint-wise assumption is illustrated by projecting a coupled uncertainty set onto each constraint's relevant parameter.
Robust optimization treats decisions as fixed before uncertainty is revealed, with responsibility and hard-constraint requirements limited to data inside a prespecified uncertainty set.
A factor model represents uncertain constraint data as an affine function a + P ζ of a lower-dimensional primitive uncertain parameter ζ.The paper notes that the resulting uncertain parameter P ζ can have much higher dimension than the primitive parameter.
The robust counterpart removes the worst-case ∀ζ constraint quantifier through worst-case reformulation, duality, and introduction of auxiliary variables, yielding linear constraints in x and w for polyhedral uncertainty.For other uncertainty classes, tractable counterparts may require conic duality or general convex reformulations.
When a tractable robust reformulation is unavailable, the adversarial approach iteratively solves a finite-scenario problem and adds scenarios for the uncertain parameters.The procedure begins with a finite scenario set, initially containing the nominal scenario.
Adjustable robust optimization allows second-stage decisions y(ζ) to respond to realized data, but practical formulations often restrict them to affine or linear decision rules.These adjustable decisions are less conservative than classic robust optimization, while affine adjustable counterparts can preserve comparable computational complexity under fixed recourse.

3 Choosing the uncertainty set

Choosing the uncertainty set requires balancing robustness against the set’s size and tractability. The paper discusses data-based constructions, probability guarantees, and common pitfalls in interpreting or specifying these sets.

Box uncertainty covers the full range of each component and guarantees constraint protection, but can be overly pessimistic.Smaller sets can still make constraints “almost never” violated.
Ellipsoidal and budgeted polyhedral uncertainty sets offer alternatives when box uncertainty is too pessimistic.Ellipsoidal sets can yield better objective values for a fixed ε, while budgeted sets produce a more tractable LP robust counterpart.
For an uncertain LP, ellipsoidal uncertainty leads to a conic quadratic formulation, whereas budgeted uncertainty leads to a linear formulation.The trade-off is objective quality versus computational tractability for a fixed probability parameter ε.
To avoid intractability or trivial solutions, uncertainty may need to be defined separately for each constraint or intersected with a box.This is especially relevant when uncertainty-set terms involve components that do not appear in a given constraint.
Uncertainty sets can be constructed from historical data, statistical tests, risk measures, distributional information, or probability-vector divergences.Historical-data approaches may require fewer assumptions, while φ-divergence sets for probability vectors can contain the true vector with approximate probability 1−ε and retain tractable robust counterparts.
Probability guarantees depend on the available distributional assumptions and must not be confused with the probability that a robust constraint holds.The paper shows that an uncertainty set containing the true parameter with probability 1−ε can imply a much larger constraint-satisfaction probability.

4 Linearly adjustable robust counterpart: linear in what?

Linearly adjustable robust counterparts approximate adjustable decisions through different choices of what the decision rule is linear in. The choice affects conservatism, interpretability, and use of available information.

Adjustable variables depend on uncertain realizations, while fixed-recourse quantities do not depend on uncertainty.The paper introduces two affine decision-rule choices for this setting.
AARC 1 makes y linear in ζ, whereas AARC 2 makes y linear in a + P ζ.AARC 2 is at least as conservative as AARC 1, and the two are equivalent when the transformation is injective on Z.
The choice between decision rules depends on factors including information availability, conservatism, interpretability, and computational considerations.The paper states that these factors influence the selection of a particular AARC.
An information-base matrix P allows decisions to be linear in P ζ rather than directly in ζ.This represents uncertainty through an information structure tied to observed data.
With partially distinguishable demand scenarios, AARC 2 yields a decision rule that directly relates to previously observed demand and is easier to interpret.When first-period demand is 10, two scenarios cannot be distinguished, motivating the information-based representation.

5 Adjustable integer variables

Adjustable robust optimization models wait-and-see integer decisions by partitioning the uncertainty set, improving objective values but increasing model size with the number of subsets.

Modeling adjustable integer variables: Adjustable robust optimization partitions the uncertainty set into disjoint subsets and assigns separate integer decisions to each subset.This models decisions made after observing part of the uncertain parameter.
Modeling adjustable integer variables: ARC is at least as good as non-adjustable RC because it can select different integer-variable values for different uncertainty subsets.The non-adjustable model uses one decision, whereas ARC uses a specific decision for each subset.
Numerical example: 7% improvement in the objective value is obtained with the adjustable reformulation relative to the non-adjustable problem in the toy example.
Numerical example: Reoptimization preserves worst-case performance while improving average performance, and average performance improves as the number of subsets increases.The comparison reports equal worst-case performance between ARC and re-opt for a fixed number of subsets, with significantly better averages for re-opt.
Tractability: The adjustable reformulation increases variables and constraints by a factor m, so many integer variables can make the resulting model intractable.More subsets can improve the objective by allowing greater decision flexibility, creating a tradeoff between optimality and computational complexity.

6 Robust counterparts of equivalent deterministic problems are not necessarily equivalent

Equivalent deterministic reformulations can produce different robust counterparts because robust optimization treats uncertainty constraint-wise. Reformulation choices must therefore preserve how uncertainty is distributed across constraints.

General principle: Equivalent deterministic formulations are not necessarily equivalent after robustification because uncertainty may be split across separate constraints.The paper attributes the difference to the constraint-wise nature of robust optimization.
Reformulation examples: Adding a slack variable to an uncertain inequality can turn it into an overly restrictive uncertain equality, changing the robust feasible region.The paper advises avoiding uncertain equalities and introducing slack variables unless they are adjustable.
General principle: Splitting uncertainty across constraints can shrink the feasible set from a line segment to the single solution x = (0, 0).In the example, one robust formulation permits solutions (θ, −θ), −1 ≤θ ≤1, while the other permits only x = (0, 0).
Reformulation examples: Applying the Charnes–Cooper transformation directly to a robust fractional problem is not equivalent because uncertainty becomes split between the objective and a constraint.The paper recommends solving a robust linear problem for fixed λ and searching for the smallest feasible λ.
Reformulation examples: Standard linearization is valid for products of binary variables when the added constraints contain no uncertain parameters, but not for binary–continuous products when uncertainty is split.A separate correct reformulation is given for the binary–continuous case.
Reformulation examples: For at-least-K robust constraints, a constraint-wise formulation is overly conservative when at least K constraints must hold simultaneously for every uncertainty realization.The paper does not provide a correct general model and suggests that an adversarial approach might be useful.

7 How to deal with equality constraints?

Uncertain equality constraints can drastically restrict feasibility, so practitioners should avoid them when possible or eliminate variables carefully using supported reformulations.

General guidance: Uncertain equality constraints should generally be avoided because they can drastically restrict feasibility or cause infeasibility.The paper particularly warns against using non-adjustable slack variables, which create equality constraints.
Alternative formulations: Transportation demand constraints may be converted from equalities to inequalities when problem structure makes those inequalities tight at optimality.
Variable elimination: Eliminating x2 is computationally more attractive than eliminating x1 or x3 because it keeps the resulting uncertainty linear.The alternatives make uncertainty nonlinear in the resulting inequality.
Variable elimination: Different choices of variables to eliminate can lead to different optimization problems, so elimination requires attention to the resulting uncertain structure.
Adjustable variables: When state or analysis variables have non-uncertain coefficients and the equality is linear in uncertainty, linear decision rules are equivalent to eliminating those variables.Substitution can reduce the number of additional variables required.

8 On maximin and minimax formulations of RC

This section distinguishes robust counterpart formulations from maximin and minimax interpretations, showing their equivalence depends on constraint-wise uncertainty.

8 On maximin and minimax formulations of RC: The uncertain LP places coefficient matrix A in uncertainty set U, and its robust counterpart requires constraints to hold across that uncertainty.
8 On maximin and minimax formulations of RC: The reformulation of (R-LP) as (RF) is valid when uncertainty is constraint-wise, but may fail when that condition does not hold.
8 On maximin and minimax formulations of RC: The phrase “RO optimizes for the worst case A” is too vague, because the relevant formulation determines how uncertainty and feasibility are treated.
8 On maximin and minimax formulations of RC: The maximin reformulation is usually not equivalent to (R-LP), since some x yield no A in U satisfying Ax ≤ d and therefore an empty minimization set.
8 On maximin and minimax formulations of RC: Under constraint-wise uncertainty, dualizing the inner maximization in (RF) establishes equivalence with the robust formulation under regularity conditions.
8 On maximin and minimax formulations of RC: Constraint-wise uncertainty with disjoint uncertainty sets preserves val(R-LP) = val(RF), whereas dependent uncertainty across constraints may break the equivalence.
Example: The toy example uses two interdependent constraints linked through an ellipsoidal uncertainty set, violating the constraint-wise condition.

9 Quality of robust solution

The paper evaluates robust-solution quality through simulation, emphasizing uncertainty-set and distribution choices, performance gaps, and statistical comparisons between solutions.

A Monte Carlo assessment identifies four focus points and uses statistical tests to compare solution quality.
Choice of the uncertainty set: The evaluation uncertainty set should reflect real-life uncertainty and may differ from the optimization set to reduce conservatism or assess performance realistically.
Choice of the probability distribution: Simulation results should be checked for sensitivity to the assumed probability distribution when that distribution is ambiguous.
Choice of the sampling method: For multivariate uncertainty, hit-and-run sampling can be more efficient than rejection sampling for difficult uncertainty-set geometries.
Choice of the performance characteristics: Objective uncertainty is evaluated using actual objective values, including worst-case, average, and standard-deviation performance measures.
Choice of the performance characteristics: Reformulated models should be evaluated through the original model because auxiliary constraints introduced by reformulation may not represent practically meaningful violations.
Performance characteristics for uncertainty in the constraints: For uncertain constraints, report positive-violation probability and violation distributions, optionally including the average number of violated constraints.
The price of robustness measures the difference between robust worst-case and nominal objective values, while the price of uncertainty compares robust performance with perfect hindsight.

10 RC may take better “here and now” decisions than AARC

The section compares static and adjustable robust decisions with folding-horizon reoptimization, showing that RC can choose better initial decisions than AARC for the original objective.

Linear decision rules approximate more complicated policies, while folding-horizon variants reoptimize remaining periods after uncertainty is observed.
The warehouse example models two ordering periods with uncertain demand drawn from a ball around 5 and uses folding-horizon reoptimization.
10.8 is the approximate worst-case performance for the folding-horizon strategy when the initial order quantity is approximately 2.3.
The RC chooses q1 ≈ 4.4 and yields worst-case folding-horizon costs of 14.9, versus 17.8 for nominal and 16.8 for AARC.
Although AARC has a better auxiliary objective value and contains the RC feasible region, it can perform worse on the original objective because both optimize approximations.
The retailer-supplier experiment evaluates nominal, RC-FH, and AARC-FH solutions using average and worst-case performance.
The paper’s broader practical comparison includes mean costs and mean price-of-uncertainty measures for the retailer-supplier problem.

11 Conclusion

The paper concludes with a practical guide for applying robust optimization, combining general procedures, practical insights, and numerical examples.

The paper provides a general procedure and practical insights for applying robust optimization successfully.
Robust reformulations of equivalent deterministic optimization problems may not remain equivalent.
In multi-stage problems, re-optimizing at each stage using static RO or nominal data may outperform adjustable RO solutions.
The actual probability guarantee of an uncertainty set is often higher than the guarantee approximated by a safe approximation technique.
The paper addresses uncertainty-set choice, worst-case interpretation, decision rules, equality constraints, integer adjustable variables, and robustness comparison.