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#

Feasible Region

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:

Feasible Region

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

Counter Plot

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*}\]