# Robust Linear Programming with Ellipsoidal Uncertainty¶

Description: AMPL Modeling Tips #6: Robust Linear Programming

Tags: highlights, modeling-tips, conic

Notebook author: Gleb Belov <gleb@ampl.com>

```
# Install dependencies
%pip install -q amplpy pandas
```

```
# Google Colab & Kaggle integration
from amplpy import AMPL, ampl_notebook
ampl = ampl_notebook(
modules=["mosek", "gurobi"], # modules to install
license_uuid="default", # license to use
) # instantiate AMPL object and register magics
```

# Diet problem with uncertain costs¶

In the diet problem we want to find a diet that satisfies certain nutritional requirements while also minimizing the total cost.

**What if the costs were not known exactly?**

One simple approach is via robust optimization using ellipsoidal uncertainty as follows:

```
var t >= 0; # Auxiliary variable
minimize Total_Cost:
sum {j in FOOD} cost[j] * Buy[j] + t; # Added to the objective
subject to Ellipsoid:
t >= sqrt(sum {j in FOOD} (0.4 * cost[j] * Buy[j])^2); # Second-order cone
```

Let’s consider a simplified version of the diet problem and let’s consider uncertainty:

We have just two types of food

We just want to satisfy the required number of calories per day

**The costs are not known exactly**

If the costs were known exactly, we could model this problem as follows:

```
set NUTR;
set FOOD;
param cost {FOOD} > 0;
param calories {FOOD} >= 0;
param min_calories;
param max_calories;
var Buy {j in FOOD} >= 0;
minimize Total_Cost:
sum {j in FOOD} cost[j] * Buy[j];
subject to Required_Calories:
min_calories <= sum {i in FOOD} calories[i] * Buy[i] <= max_calories;
```

## Since there is uncertainty we can do the following modifications:¶

```
var t >= 0; # Auxiliary variable
minimize Total_Cost:
sum {j in FOOD} cost[j] * Buy[j] + t; # Added to the objective
subject to Ellipsoid:
t >= sqrt(sum {j in FOOD} (0.4 * cost[j] * Buy[j])^2); # Second-order cone
```

```
%%ampl_eval
reset;
set NUTR;
set FOOD;
param cost {FOOD} > 0;
param calories {FOOD} >= 0;
param min_calories;
param max_calories;
param robust default 1;
var Buy {j in FOOD} >= 0;
var t >= 0; # Auxiliary variable
minimize Total_Cost:
sum {j in FOOD} cost[j] * Buy[j] + t; # Added to the objective
subject to Required_Calories:
min_calories <= sum {i in FOOD} calories[i] * Buy[i] <= max_calories;
subject to Ellipsoid{if robust}:
t >= sqrt(sum {j in FOOD} (0.4 * cost[j] * Buy[j])^2); # Second-order cone
```

```
ampl.set["FOOD"] = ["BEEF", "CHK"]
ampl.param["cost"] = {"BEEF": 1, "CHK": 1}
ampl.param["min_calories"] = 2000
ampl.param["max_calories"] = 2500
ampl.param["calories"] = {"BEEF": 250, "CHK": 239}
```

## Solving Robust and non-Robust models with MOSEK¶

```
%%ampl_eval
printf "> Not robust:\n";
option solver mosek;
let robust := 0;
solve;
display Buy, Total_Cost;
printf "> Robust:\n";
let robust := 1;
solve;
display Buy, Total_Cost - t;
```

```
> Not robust:
MOSEK 10.0.16: MOSEK 10.0.16: optimal; objective 8
0 simplex iterations
Buy [*] :=
BEEF 8
CHK 0
;
Total_Cost = 8
> Robust:
MOSEK 10.0.16: MOSEK 10.0.16: optimal; objective 10.4815553
0 simplex iterations
6 barrier iterations
Buy [*] :=
BEEF 4.49848
CHK 3.66268
;
Total_Cost - t = 8.16116
```

## Solving Robust and non-Robust models with Gurobi¶

```
%%ampl_eval
printf "> Not robust:\n";
option solver gurobi;
let robust := 0;
solve;
display Buy, Total_Cost;
printf "> Robust:\n";
let robust := 1;
solve;
display Buy, Total_Cost - t;
```

```
> Not robust:
Gurobi 10.0.1: Gurobi 10.0.1: optimal solution; objective 8
0 simplex iterations
Buy [*] :=
BEEF 8
CHK 0
;
Total_Cost = 8
> Robust:
Gurobi 10.0.1: Gurobi 10.0.1: optimal solution; objective 10.48155551
0 simplex iterations
5 barrier iterations
Buy [*] :=
BEEF 4.49905
CHK 3.66208
;
Total_Cost - t = 8.16113
```

**We see that the robust solution balances the choices, while LP strictly prefers just 1 of the products. We exchanged some optimality for robustness.**

Ellipsoidal uncertainty is of the less conservative kind: Introduction.

Documentation on AMPL conic and extended modeling can be found in the MP Modeling Guide.

## Formal explanation¶

Consider a linear optimization problem of the form:

$$\min_x c^T x : Ax \ge b, \ x\ge 0$$

In practice, the objective coefficients $c$ may not be known perfectly. Assume that we only know that (with high probability) $c \in E$, where $E$ is a given ellipsoid:

$$E = { \widehat{c} + Ru : |u|_2 \le 1},$$

with center $\widehat{c} \in \mathbf{R}^n$ and $R \in \mathbf{R}^{n \times k}$. In robust optimization, we seek to minimize the objective for the worst-case scenario:

$$\max_{c \in E} c^Tx = \widehat{c}^Tx + \max_{|u|_2 \le 1} x^TR u = \widehat{c}^Tx + |R^Tx|_2,$$

where we used that $\max_{||u||_2\le1} v^Tu = (v^Tv)/||v||_2 = ||v||_2$. The robust problem is equivalent to

$$\begin{equation} \min_x \widehat{c}^T x + ||R^Tx||_2 : Ax \ge b, \ x\ge 0.\end{equation}$$

This can be visualized for the 2D case. Assume we have two kinds of food with prices $c_1$, $c_2$ and calories per unit $a_1$, $a_2$. Buying amounts $x_1$, $x_2$ of them, we optimize the LP

\begin{align*} \min\quad &c_1x_1 + c_2x_2 \ s.t.\quad &a_1x_1 + a_2x_2 \ge b, \ &x_1, x_2 \ge 0. \end{align*}

Adding an ellipsoidal uncertainty term in the objective, we obtain the problem

\begin{align*} \min\quad &\widehat{c}_1x_1 + \widehat{c}_2x_2 + ||R^Tx||_2 \ s.t.\quad &a_1x_1 + a_2x_2 \ge b, \ &x_1, x_2 \ge 0. \end{align*}

A graphical representation of the feasible set and linear vs. robust objectives:

We see that the robust solution balances the choices, while LP strictly prefers just 1 of the products.

Note that the contour line passing through the origin (and corresponding to objective value 0) is piecewise-linear

The robust LP (1) can be reformulated as a conic quadratic problem:

\begin{align*} \min \quad &\widehat{c}^T x + t \ \text{s.t.}\quad &Ax \ge b, \ &(t, R^Tx) \in \text{QuadCone}(n), \ &x \ge 0. \end{align*}