Operations Research – Stochastic Methods
Robust Optimization
Lecturer: Jannis Kurtz
Section Business Analytics
Intended Learning Outcomes
1. Apply the robust optimization approach to linear problems
2. Reflect on the construction of uncertainty sets
3. Apply the robust optimization approach with budgeted uncertainty sets.
Robust Optimization
In contrast to stochastic optimization, in robust optimization we do not consider any probability distributions on
the uncertain parameters.
Instead: define uncertainty set U which contains all possible parameter realizations (scenarios) which may occur
Example
A truck can carry pallets of at most 7.5 tons. There are two types of pallets.
• One pallet of type A weighs 0.95 tons and one pallet of type B weighs 1.35 tons
• The profit for one pallet of type A is 110 EUR and for one of type B 140 EUR
How many pallets of which type should be transported?
Optimal solution: x = (5,2)
Example
You realize that the weight of each pallet can deviate from time to time. You are estimating that the weight of each
pallet can deviate up to 2% of its nominal value (which is 0.95 tons and 1.35 tons, respectively).
This means the uncertain weights of pallets A can be any value in the interval
and the weights of pallets B can be any value in the interval
Assignment: Check if the deterministic solution x=(5,2) is still feasible for all possible weights.
Example
How can we find a solution which is robust against the uncertainty, i.e. which is feasible for all possible weights in
the uncertainty set
Robust Optimization Problem:
Since both parameters can be chosen in their respective intervals independently, this is equivalent to:
Assignment
Reformulate the robust problem into a problem without uncertainty:
The Robust Optimization Problem
In general, assume we have a given deterministic problem
Assume the constraint parameters ai of constraint i are uncertain and lie in an uncertainty set Ui for all i=1,..,m
Then the robust optimization problem is
The Robust Optimization Problem
The robust optimization problem can always be reformulated as
Box Uncertainty
Assume that every constraint parameter can vary in an interval independently of all other parameters, i.e.
This is called a box uncertainty set:
Reformulation for Box Uncertainty
Let‘s consider one single robust constraint:
Assume we have a box uncertainty set, i.e.
Since all variables xi are non-negative we can reformulate the robust constraint as:
The latter is a deterministic constraint, so no uncertainty involved anymore!
We can reformulate every constraint in that way and then use a standard method to solve linear problems.
Note: the same works for integer or real variables x
Assignment
Consider the following robust optimization problem
Attention!
with and
Derive a linear formulation for this robust problem.
Objective Uncertainty
We assume next that the uncertain parameters of our problem only appear in the objective function.
More precisely: we assume that the cost coefficients ci are uncertain, but all constraint parameters in A are
precisely known.
Example:
• The shortest path problem with uncertain travel costs.
• Portfolio optimization with uncertain profits.
• The assignment problem with uncertain costs.
• ….
In this case the robust optimization problem is defined as:
Box Uncertainty l=(l1,l2,…,ln)
u=(u1,u2,…,un)
Assume we have a box uncertainty set
Then the robust optimization problem can be reformulated as follows:
The latter problem is a standard linear problem which can be solved by the simplex method.
The same transformation works also for positive integer variables x. Then the problem becomes a standard
linear integer problem which can be solved by the branch & bound method.
Budgeted Uncertainty
The latter approach is known to be very conservative since we calculate a solution for the worst possible situation,
namely if all parameters take their worst value in the interval.
In practice it nearly ever happens, that all uncertain parameters take their worst value.
That‘s why a popular choice for the uncertainty set is the so called budgeted uncertainty set.
Main Idea: instead of assuming that all parameters can vary independently in their intervals,
we only allow at most k parameters to deviate from their mean value at the same time.
Budgeted Uncertainty
Let‘s consider the cost vector c. Assume each cost parameter ci can take any values in the interval
where is the mean value of the parameter and di the maximum deviation from the mean value.
Then the budgeted uncertainty set is defined as
for a given budget k. The budget k can be used to control the „conservativeness“.
Budgeted Uncertainty
The robust optimization problem is
For now consider an arbitrary feasible solution x and only consider the inner maximization of the objective function:
By the definition of the budgeted uncertainty set this maximization problem can be reformulated as:
That‘s a linear
optimization
problem in the
variables z.
Budgeted Uncertainty
Primal problem: Dual problem:
Instead of the primal problem we can use the dual problem in our robust optimization formulation. Replace the inner
maximization problem in the robust problem by its dual formulation:
That‘s a linear
optimization problem in
the variables x,w,y. This
can be solved by the
simplex method.
Assignment
Consider the following production problem
Assume that only the objective parameters are uncertain and you estimated that each parameter can be up to 3% larger than the
given value. Additionally you assume that at most 2 parameters can deviate from their mean value at the same time.
Assignment
Derive the robust optimization problem and reformulate it as linear problem by using dualization.
Uncertainty Set Size
Assume we have two uncertainty sets, U1 and U2 and U2 contains U1 and is larger than U1, i.e.
For the optimal values of the two corresponding robust optimization problems it always holds
That means smaller sets provide better solutions! But at the same time the better solution is less robust!
There is always a tradeoff between robustness and solution quality!
Robust Binary Optimization
We consider now optimization problems which only have binary variables and where the uncertainty only appears in the
objective function:
Examples:
• Shortest Path Problem
• Spanning Tree Problem
• Assignment Problem
• …..
In this case the robust optimization problem is
Budgeted Uncertainty
We can use the same dualization trick when our variables x are binary. Hence, the robust optimization problem for binary
problems with objective uncertainty is given as:
It is easy to see that the optimal yi has the value
Since xi is either 0 or one this is equivalent to
Budgeted Uncertainty
Substituting the latter equation into the yi in the objective function leads to the problem
By a similar argumentation as for the news vendor problem, one can show that the only values of the variable w which we
have to consider to find an optimal solution are:
For one fixed w* the problem reduces to a version of the original binary problem (without uncertainty):
Budgeted Uncertainty
This result was proved for the first time in the seminal paper (see Section 3):
Bertsimas, D., & Sim, M. (2003). Robust discrete optimization and network flows. Mathematical programming, 98(1), 49-71.
