AMPL Modeling Tips #6: Robust Linear Programming with Ellipsoidal Uncertainty

Announcements
,
1

Sometimes values are not known exactly

Feasible Region

In the diet problem we want to find a diet that satisfies certain nutricial requiments while also minimizing the total cost. What if the costs were not know exactly?

One simple approach is via robust optimization with 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

Open In Colab

Simplified diet problem

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

Complete model

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

Solving with MOSEK

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: optimal; objective 8
0 simplex iterations
Buy [*] :=
BEEF  8
 CHK  0
;

Total_Cost = 8

> Robust:
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 with Gurobi

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: optimal solution; objective 8
0 simplex iterations
Buy [*] :=
BEEF  8
 CHK  0
;

Total_Cost = 8

> Robust:
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.

[On LinkedIn] [On Twitter]

1 Like