Added 18/06/2025
Archetype
quadratic_bilevel
Datasets
Dimension
{
"x": 2,
"y": 2,
"F": 1,
"G": 5,
"H": 0,
"f": 1,
"g": 6,
"h": 0
}
Solution
{
"optimality": "global",
"x": [25,30],
"y": [5,10],
"F": 65,
"G": [0,25,30,25,20],
"H": [],
"f": -800,
"g": [5,0,15,20,15,10],
"h": []
}
Dimension
{
"x": 2,
"y": 2,
"F": 1,
"G": 4,
"H": 0,
"f": 1,
"g": 6,
"h": 0
}
Solution
{
"optimality": "global",
"x": [0.2,2],
"y": [4,4.6],
"F": 2231.727818,
"G": [0,0,0.2,2],
"H": [],
"f": 565.774477,
"g": [0,0,0,0,4,4.6],
"h": []
}
Dimension
{
"x": 1,
"y": 1,
"F": 1,
"G": 1,
"H": 0,
"f": 1,
"g": 4,
"h": 0
}
Solution
{
"optimality": "global",
"x": [1],
"y": [0],
"F": -9,
"f": 0
}
Dimension
{
"x": 4,
"y": 4,
"F": 1,
"G": 9,
"H": 0,
"f": 1,
"g": 12,
"h": 0
}
Solution
{
"optimality": "unknown"
}
Dimension
{
"x": 1,
"y": 2,
"F": 1,
"G": 2,
"H": 0,
"f": 1,
"g": 3,
"h": 0
}
Solution
{
"optimality": "global",
"x": [2],
"y": [6,0],
"F": 2,
"G": [0,2],
"f": 12,
"g": [0,6,0]
}
Dimension
{
"x": 2,
"y": 2,
"F": 1,
"G": 4,
"H": 0,
"f": 1,
"g": 7,
"h": 0
}
Solution
{
"optimality": "global",
"x": [25,30],
"y": [5,10],
"F": -800,
"G": [25,30,25,20],
"f": 65,
"g": [0,5,0,15,20,15,10]
}
Dimension
{
"x": 1,
"y": 1,
"F": 1,
"G": 0,
"H": 0,
"f": 1,
"g": 3,
"h": 0
}
Solution
{
"optimality": "global",
"x": [1.25],
"y": [0.25],
"F": -0.4375,
"G": [],
"f": -0.1875,
"g": [0,0.5,0]
}
Dimension
{
"x": 4,
"y": 2,
"F": 1,
"G": 0,
"H": 0,
"f": 1,
"g": 6,
"h": 0
}
Solution
{
"optimality": "global",
"x": [1.25,0.5,1,1],
"y": [0.25,0.5],
"F": -1.6875,
"G": [],
"f": -0.40625,
"g": [0,1,0,2,0.5,0]
}
Dimension
{
"x": 4,
"y": 2,
"F": 1,
"G": 0,
"H": 0,
"f": 1,
"g": 6,
"h": 0
}
Solution
{
"optimality": "global",
"x": [0.13085,0.05195,0.1022,0.0674],
"y": [0.025,0.05],
"F": -1.6875,
"G": [],
"f": -0.40625,
"g": [0,1,0,2,0.5,0]
}
Dimension
{
"x": 1,
"y": 1,
"F": 1,
"G": 2,
"H": 0,
"f": 1,
"g": 3,
"h": 0
}
Solution
{
"optimality": "global",
"x": [1],
"y": [3],
"F": -8,
"G": [7,1],
"f": -21,
"g": [0,3,7]
}
Dimension
{
"x": 1,
"y": 1,
"F": 1,
"G": 2,
"H": 0,
"f": 1,
"g": 2,
"h": 0
}
Solution
{
"optimality": "global",
"x": [-1],
"y": [1],
"F": -1,
"G": [0,2],
"f": -1,
"g": [1,0]
}
Dimension
{
"x": 2,
"y": 2,
"F": 1,
"G": 4,
"H": 0,
"f": 1,
"g": 4,
"h": 0
}
Solution
{
"optimality": "global",
"x": [0,-1],
"y": [1,2],
"F": 5,
"G": [1,0,1,2],
"f": -2,
"g": [0,1,0,2]
}
Dimension
{
"x": 2,
"y": 2,
"F": 1,
"G": 4,
"H": 0,
"f": 1,
"g": 3,
"h": 0
}
Solution
{
"optimality": "global",
"x": [1,-1],
"y": [0,1],
"F": 2,
"G": [2,0,0,2],
"f": -1,
"g": [0,2.5,1]
}
Dimension
{
"x": 2,
"y": 2,
"F": 1,
"G": 4,
"H": 0,
"f": 1,
"g": 4,
"h": 0
}
Solution
{
"optimality": "global",
"x": [-1,-1],
"y": [2,2],
"F": -1,
"G": [0,0,2,0.25],
"f": -4,
"g": [2,2,0,0]
}
Dimension
{
"x": 2,
"y": 2,
"F": 1,
"G": 0,
"H": 0,
"f": 1,
"g": 4,
"h": 0
}
Solution
{
"optimality": "global",
"x": [0,0],
"y": [1,1],
"F": -6,
"G": [],
"f": 0,
"g": [0,0,1,1]
}
Dimension
{
"x": 3,
"y": 3,
"F": 1,
"G": 0,
"H": 0,
"f": 1,
"g": 5,
"h": 0
}
Solution
{
"optimality": "unknown",
"x": [0.5,0.5,0],
"y": [0,0,2],
"F": -12.5,
"G": [],
"f": 0,
"g": [0,0,0,0,2]
}
Dimension
{
"x": 2,
"y": 2,
"F": 1,
"G": 0,
"H": 0,
"f": 1,
"g": 4,
"h": 0
}
Solution
{
"optimality": "global",
"x": [0.5,0.5],
"y": [0.5,0.5],
"F": -1,
"G": [],
"f": 0,
"g": [0,0,1,1]
}
Dimension
{
"x": 2,
"y": 2,
"F": 1,
"G": 0,
"H": 0,
"f": 1,
"g": 4,
"h": 0
}
Solution
{
"optimality": "global",
"x": [0.8660254037844386,0.8660254037844386],
"y": [0.8660254037844386,0.8660254037844386],
"F": -2.1961524227066325,
"G": [],
"f": 0,
"g": [0.3660254037844386,0.3660254037844386,0.6339745962155614,0.6339745962155614]
}
Dimension
{
"x": 2,
"y": 2,
"F": 1,
"G": 4,
"H": 0,
"f": 1,
"g": 7,
"h": 0
}
Solution
{
"optimality": "global",
"x": [0,0],
"y": [-10,-10],
"F": 60,
"G": [0,0,50,50],
"f": -600,
"g": [10,10,30,0,0,30,30]
}
Dimension
{
"x": 1,
"y": 1,
"F": 1,
"G": 5,
"H": 0,
"f": 1,
"g": 2,
"h": 0
}
Solution
{
"optimality": "global",
"x": [3],
"y": [5],
"F": -4,
"G": [2,5,1,3,5],
"f": -25,
"g": [5,5]
}
Dimension
{
"x": 1,
"y": 2,
"F": 1,
"G": 0,
"H": 0,
"f": 1,
"g": 2,
"h": 0
}
Solution
{
"optimality": "global",
"x": [0],
"y": [0,0],
"F": 0,
"G": [],
"f": 0,
"g": [0,0]
}
Dimension
{
"x": 1,
"y": 1,
"F": 1,
"G": 2,
"H": 0,
"f": 1,
"g": 1,
"h": 0
}
Solution
{
"optimality": "best_known",
"x": [93.33333333],
"y": [26.66666667],
"F": -3266.6666665499997,
"G": [93.33333333,106.66666667],
"f": -711.1111111555551,
"g": [26.66666667]
}
Dimension
{
"x": 1,
"y": 1,
"F": 1,
"G": 0,
"H": 0,
"f": 1,
"g": 0,
"h": 0
}
Solution
{
"optimality": "global",
"x": [-0.5],
"y": [-0.5],
"F": -0.25,
"G": [],
"f": -0.125,
"g": []
}
Dimension
{
"x": 1,
"y": 1,
"F": 1,
"G": 1,
"H": 0,
"f": 1,
"g": 1,
"h": 0
}
Solution
{
"optimality": "global",
"x": [1],
"y": [0],
"F": 1,
"G": [0],
"f": 0,
"g": [0]
}
Dimension
{
"x": 1,
"y": 1,
"F": 1,
"G": 0,
"H": 0,
"f": 1,
"g": 0,
"h": 0
}
Solution
{
"optimality": "global",
"x": [0.5],
"y": [0.5],
"F": 0.5,
"G": [],
"f": -1,
"g": []
}
Dimension
{
"x": 1,
"y": 2,
"F": 1,
"G": 1,
"H": 0,
"f": 1,
"g": 3,
"h": 0
}
Solution
{
"optimality": "global",
"x": [0.5],
"y": [0.5,0],
"F": 0.5,
"G": [0],
"f": 0.5,
"g": [0,0.5,0]
}
Dimension
{
"x": 1,
"y": 1,
"F": 1,
"G": 2,
"H": 0,
"f": 1,
"g": 3,
"h": 0
}
Solution
{
"optimality": "global",
"x": [0.8],
"y": [0.4],
"F": 0.8,
"G": [1.8,0.2],
"f": -0.4,
"g": [0,0.4,0.6]
}
Dimension
{
"x": 1,
"y": 1,
"F": 1,
"G": 2,
"H": 0,
"f": 1,
"g": 2,
"h": 0
}
Solution
{
"optimality": "global",
"x": [1],
"y": [0],
"F": -0.5,
"G": [1,0],
"f": 0,
"g": [0,1]
}
Dimension
{
"x": 1,
"y": 1,
"F": 1,
"G": 0,
"H": 0,
"f": 1,
"g": 0,
"h": 0
}
Solution
{
"optimality": "global",
"x": [10.0163],
"y": [0.8197],
"F": 79.32617377999999,
"G": [],
"f": -0.3321014549999859,
"g": []
}
Dimension
{
"x": 1,
"y": 1,
"F": 1,
"G": 2,
"H": 0,
"f": 1,
"g": 2,
"h": 0
}
Solution
{
"optimality": "global",
"x": [0],
"y": [1],
"F": -1,
"G": [0.5,0.5],
"f": 0,
"g": [2,0]
}
Dimension
{
"x": 1,
"y": 2,
"F": 1,
"G": 2,
"H": 0,
"f": 1,
"g": 3,
"h": 0
}
Solution
{
"optimality": "best_known",
"x": [0.8438],
"y": [0.7657,0],
"F": -2.07690507,
"G": [0.8438,1.1562000000000001],
"f": -0.5862964900000003,
"g": [1.1562,0.7657,0]
}
Dimension
{
"x": 2,
"y": 3,
"F": 1,
"G": 3,
"H": 0,
"f": 1,
"g": 4,
"h": 0
}
Solution
{
"optimality": "best_known",
"x": [0.609,0.391],
"y": [0,0,1.828],
"F": 0.642584,
"G": [0,0.609,0.391],
"f": 1.670792,
"g": [0.001,0,0,1.828]
}
Dimension
{
"x": 2,
"y": 2,
"F": 1,
"G": 0,
"H": 0,
"f": 1,
"g": 4,
"h": 0
}
Solution
{
"optimality": "infeasible",
"x": [0.97,3.14],
"y": [2.6,1.8],
"F": -8.91995,
"G": [],
"f": -6.053999999999999,
"g": [1.0658,-0.0005999999999999339,2.6,1.8]
}
Dimension
{
"x": 2,
"y": 2,
"F": 1,
"G": 0,
"H": 0,
"f": 1,
"g": 4,
"h": 0
}
Solution
{
"optimality": "best_known",
"x": [0.28,0.48],
"y": [2.34,1.03],
"F": -7.562950000000001,
"G": [],
"f": -0.5799499999999999,
"g": [1.74922,0.002990000000000048,2.34,1.03]
}
Dimension
{
"x": 2,
"y": 2,
"F": 1,
"G": 0,
"H": 0,
"f": 1,
"g": 4,
"h": 0
}
Solution
{
"optimality": "infeasible",
"x": [20.26,42.81],
"y": [3,3],
"F": -12,
"G": [],
"f": -112.71000000000001,
"g": [-0.0009999999999998899,-0.0009999999999998899,3,3]
}
Dimension
{
"x": 2,
"y": 2,
"F": 1,
"G": 0,
"H": 0,
"f": 1,
"g": 4,
"h": 0
}
Solution
{
"optimality": "best_known",
"x": [2,0.06],
"y": [2,0],
"F": -3.59964,
"G": [],
"f": -2,
"g": [2.666,0,2,0]
}
Dimension
{
"x": 2,
"y": 2,
"F": 1,
"G": 0,
"H": 0,
"f": 1,
"g": 4,
"h": 0
}
Solution
{
"optimality": "best_known",
"x": [2.42,-3.65],
"y": [0,1.58],
"F": -3.15391,
"G": [],
"f": -16.2898,
"g": [0.41999999999999993,2.52614,0,1.58]
}
Dimension
{
"x": 2,
"y": 2,
"F": 1,
"G": 1,
"H": 0,
"f": 1,
"g": 3,
"h": 0
}
Solution
{
"optimality": "global",
"x": [0,0],
"y": [0,0],
"F": 0,
"G": [0],
"f": 0,
"g": [0,0,0]
}
Dimension
{
"x": 1,
"y": 1,
"F": 1,
"G": 2,
"H": 0,
"f": 1,
"g": 3,
"h": 0
}
Solution
{
"optimality": "global",
"x": [1],
"y": [3],
"F": -8,
"G": [1,7],
"f": -21,
"g": [0,3,7]
}
Dimension
{
"x": 1,
"y": 1,
"F": 1,
"G": 3,
"H": 0,
"f": 1,
"g": 3,
"h": 0
}
Solution
{
"optimality": "global",
"x": [10],
"y": [10],
"F": 0,
"G": [0,10,5],
"f": -900,
"g": [0,10,10]
}
Dimension
{
"x": 2,
"y": 2,
"F": 1,
"G": 3,
"H": 0,
"f": 1,
"g": 4,
"h": 0
}
Solution
{
"optimality": "global",
"x": [20,5],
"y": [10,5],
"F": -1075,
"G": [0,0,10],
"f": 100,
"g": [10,5,0,5]
}
Dimension
{
"x": 1,
"y": 1,
"F": 1,
"G": 0,
"H": 0,
"f": 1,
"g": 3,
"h": 0
}
Solution
{
"optimality": "global",
"x": [5],
"y": [2],
"F": -1,
"G": [],
"f": -15,
"g": [10,0,0]
}
Dimension
{
"x": 1,
"y": 2,
"F": 1,
"G": 1,
"H": 0,
"f": 1,
"g": 6,
"h": 0
}
Solution
{
"optimality": "unknown",
"x": [0],
"y": [0,0],
"F": 0,
"G": [0],
"f": 0,
"g": [12,-4,4,4,0,0]
}
Dimension
{
"x": 3,
"y": 8,
"F": 1,
"G": 3,
"H": 0,
"f": 1,
"g": 18,
"h": 0
}
Solution
{
"optimality": "best_known",
"x": [7,4,6],
"y": [0,0,1,0,0,0,0,0],
"F": -7,
"G": [7,4,6],
"f": 12,
"g": [0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0]
}
Dimension
{
"x": 3,
"y": 18,
"F": 1,
"G": 3,
"H": 0,
"f": 1,
"g": 38,
"h": 0
}
Solution
{
"optimality": "best_known",
"x": [0.5,4,4.5],
"y": [0,0,0,0,1,0,1,0,0,0,0,1,0,0,1,0,0,1],
"F": -4.5,
"G": [0.5,4,4.5],
"f": 32,
"g": [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,1,0,0,1,0,0,1]
}
Dimension
{
"x": 3,
"y": 18,
"F": 1,
"G": 3,
"H": 0,
"f": 1,
"g": 38,
"h": 0
}
Solution
{
"optimality": "best_known",
"x": [5,3.5,8.5],
"y": [0,0,1,0,0,0,0,1,0,0,0,1,0,0,1,0,0,1],
"F": -3.5,
"G": [5,3.5,8.5],
"f": 32,
"g": [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,1,0,0,1,0,0,1]
}
Dimension
{
"x": 2,
"y": 4,
"F": 1,
"G": 0,
"H": 0,
"f": 1,
"g": 8,
"h": 0
}
Solution
{
"optimality": "best_known",
"x": [2.5,-1],
"y": [0,1,1,0],
"F": -4,
"G": [],
"f": 14,
"g": [0,0,0,0,0,1,1,0]
}
Dimension
{
"x": 1,
"y": 4,
"F": 1,
"G": 0,
"H": 0,
"f": 1,
"g": 8,
"h": 0
}
Solution
{
"optimality": "best_known",
"x": [2.5],
"y": [0,1,0,1],
"F": -2.5,
"G": [],
"f": 14,
"g": [0,0,0,0,0,1,0,1]
}
Dimension
{
"x": 1,
"y": 1,
"F": 1,
"G": 2,
"H": 0,
"f": 1,
"g": 3,
"h": 0
}
Solution
{
"optimality": "infeasible",
"x": [4.492188],
"y": [1.523438],
"F": 22.500616367187995,
"G": [4.492188,1.523438],
"f": -1.523438,
"g": [-0.000002000000000279556,0.9843740000000007,5.9374980000000015]
}
Dimension
{
"x": 2,
"y": 3,
"F": 1,
"G": 0,
"H": 0,
"f": 1,
"g": 8,
"h": 0
}
Solution
{
"optimality": "global",
"x": [0,0.75],
"y": [0,0.5,0],
"F": 2.625,
"G": [],
"f": -0.5,
"g": [0.5,0,0,0,0.75,0,0.5,0]
}
Dimension
{
"x": 1,
"y": 1,
"F": 1,
"G": 2,
"H": 0,
"f": 1,
"g": 2,
"h": 0
}
Solution
{
"optimality": "global",
"x": [0.25],
"y": [0],
"F": 0.5,
"G": [0.25,0.75],
"f": -0.5,
"g": [0,1]
}
$title quadratic_bilevel
$onText
Upper-level
===========
minimise 1/2 (x' P_upper x) + 1/2 (y' Q_upper y) + (x' R_upper y) + c_upper' x + d_upper' y
subject to A_upper * x + B_upper * y >= rhs_upper
x >= x_lower_bound
x <= x_upper_bound
y solves lower-level
Lower-level
===========
minimise 1/2 (x' P_lower x) + 1/2 (y' Q_lower y) + 1/2 (x' R_lower y) + c_lower' x + d_lower' y
subject to A_lower * x + B_lower * y >= rhs_lower
y >= y_lower_bound
y <= y_upper_bound
$offText
* Sets
Sets
i "Index for x variables"
j "Index for y variables"
m "Index for upper-level inequality constraints"
l "Index for Lower-level inequality constraints";
* Alias
Alias (i,i_);
Alias (j,j_);
* Parameters
Parameters
A_upper(m,i) "Upper-level inequality matrix A"
B_upper(m,j) "Upper-level inequality matrix B"
c_upper(i) "Upper-level objective coefficients for x"
d_upper(j) "Upper-level objective coefficients for y"
P_upper(i,i) "Upper-level quadratic form matrix P"
Q_upper(j,j) "Upper-level quadratic form matrix Q"
R_upper(i,j) "Upper-level quadratic form matrix R"
rhs_upper(m) "Upper-level inequality right hand side"
A_lower(l,i) "Lower-level inequality matrix A"
B_lower(l,j) "Lower-level inequality matrix B"
c_lower(i) "Lower-level objective coefficients for x"
d_lower(j) "Lower-level objective coefficients for y"
P_lower(i,i) "Lower-level quadratic form matrix P"
Q_lower(j,j) "Lower-level quadratic form matrix Q"
R_lower(i,j) "Lower-level quadratic form matrix R"
rhs_lower(l) "Lower-level inequality right hand side"
x_lower_bound(i) "x lower bound"
x_upper_bound(i) "x upper bound"
y_lower_bound(j) "y lower bound"
y_upper_bound(j) "y upper bound";
* Variables
Variables
x(i) "Upper-level decision variables"
y(j) "Lower-level decision variables"
obj "Objective function value";
* Data
$gdxin "/bolib3/data/quadratic_bilevel_gdx/an_et_al_2009.gdx"
$load i=i, j=j, m=m, l=l,
$load A_upper=A_upper, B_upper=B_upper, c_upper=c_upper, d_upper=d_upper,
$load P_upper=P_upper, Q_upper=P_upper, R_upper=P_upper, rhs_upper=rhs_upper,
$load A_lower=A_lower, B_lower=B_lower, c_lower=c_lower, d_lower=d_lower,
$load P_lower=P_lower, Q_lower=P_lower, R_lower=P_lower, rhs_lower=rhs_lower,
$load x_lower_bound, x_upper_bound,
$load y_lower_bound, y_upper_bound
Display c_upper;
Display c_upper;
Variables x, y, obj_val_upper, obj_val_lower;
* Equations
Equations
obj_eq_upper "Upper-level objective"
obj_eq_lower "Lower-level objective"
upper_ineq(m) "Upper-level inequality constraints"
lower_ineq(l) "Lower-level inequality constraint";
* Upper-level objective
obj_eq_upper .. obj_val_upper =e=
0.5 * sum((i,i_), x(i) * P_upper(i,i_) * x(i_))
+ 0.5 * sum((j,j_), y(j) * Q_upper(j,j_) * y(j_))
+ 1.0 * sum((i,j), x(i) * R_upper(i,j) * y(j))
+ sum(i, c_upper(i) * x(i))
+ sum(j, d_upper(j) * y(j));
* Lower-level objective
obj_eq_lower .. obj_val_lower =e=
0.5 * sum((i,i_), x(i) * P_lower(i,i_) * x(i_))
+ 0.5 * sum((j,j_), y(j) * Q_lower(j,j_) * y(j_))
+ 1.0 * sum((i,j), x(i) * R_lower(i,j) * y(j))
+ sum(i, c_lower(i) * x(i))
+ sum(j, d_lower(j) * y(j));
* Upper-level inequality constraints
upper_ineq(m) .. sum(i, A_upper(m,i)*x(i)) + sum(j, B_upper(m,j)*y(j)) =g= rhs_upper(m);
* Lower-level inequality constraint
lower_ineq(l) .. sum(i, A_lower(l,i)*x(i)) + sum(j, B_lower(l,j)*y(j)) =g= rhs_lower(l);
* Bounds
x.lo(i) = x_lower_bound(i);
x.up(i) = x_upper_bound(i);
y.lo(j) = y_lower_bound(j);
y.up(j) = y_upper_bound(j);
* Solve
model quadratic_bilevel / all /;
$echo bilevel x min obj_val_lower y obj_eq_lower, lower_ineq > "%emp.info%"
solve quadratic_bilevel us emp min obj_val_upper;
\subsection{quadratic\_bilevel}
\label{subsec:quadratic_bilevel}
% Quadratic bilevel program
For decision variables $\x\in\R^{n_x}$ and $\y\in\R^{n_y}$ and the quadratic bilevel program has the form
\begin{flalign*}
\minimise_{\x\in\R^{n_x}, \y\in\R^{n_y}} \quad
& \frac{1}{2}\x^\top {P_\upper} \x
+ \frac{1}{2}\y^\top {Q_\upper} \y
+ \x^\top {R_\upper} \y
+ {c_\upper^\top} \x
+ {d_\upper^\top} \y\\
\subjectto \quad
& {A_\upper} \x + {B_\upper} \y \geq {r_\upper}\\
& \xlb\leq \x \leq\xub \\
& y \in \argmin_{y\in\R^{n_y}}
\left\{
\begin{array}{l}
\frac{1}{2}\x^\top {P_\low} \x
+ \frac{1}{2}\y^\top {Q_\low} \y
+ \frac{1}{2}\y^\top {R_\low} \y
+ {c_\low^\top} \x
+ {d_\low^\top} \y\\
{A_\low} \x + {B_\low} \y \geq {r_\low}\\
\ylb\leq \y \leq\yub
\end{array}
\right.
\end{flalign*}
where the program is parametrised by
\begin{center}
\begin{tabular}{c c l}
\toprule
Parameter & variable name & dimension \\
\midrule
$A_\upper$ & \texttt{A\_upper} & $\in\R^{n_G \times n_x}$ \\
$B_\upper$ & \texttt{B\_upper} & $\in\R^{n_G \times n_y}$ \\
$c_\upper$ & \texttt{c\_upper} & $\in\R^{n_x}$ \\
$d_\upper$ & \texttt{d\_upper} & $\in\R^{n_y}$ \\
$P_\upper$ & \texttt{P\_upper} & $\in\R^{n_x \times n_x}$ \\
$Q_\upper$ & \texttt{Q\_upper} & $\in\R^{n_y \times n_y}$ \\
$R_\upper$ & \texttt{R\_upper} & $\in\R^{n_x \times n_y}$ \\
$r_\upper$ & \texttt{rhs\_upper} & $\in\R^{n_G}$ \\
\midrule
$A_\low$ & \texttt{A\_lower} & $\in\R^{n_g \times n_x}$ \\
$B_\low$ & \texttt{B\_lower} & $\in\R^{n_g \times n_y}$ \\
$c_\low$ & \texttt{c\_lower} & $\in\R^{n_x}$ \\
$d_\low$ & \texttt{d\_lower} & $\in\R^{n_y}$ \\
$P_\low$ & \texttt{P\_lower} & $\in\R^{n_x \times n_x}$ \\
$Q_\low$ & \texttt{Q\_lower} & $\in\R^{n_y \times n_y}$ \\
$R_\low$ & \texttt{R\_lower} & $\in\R^{n_x \times n_y}$ \\
$r_\low$ & \texttt{rhs\_lower} & $\in\R^{n_g}$ \\
\midrule
$\xlb, \xub$ & \texttt{x\_bounds} & $\in\R^{n_x}$\\
$\ylb, \yub$ & \texttt{y\_bounds} & $\in\R^{n_y}$\\
\bottomrule
\end{tabular}
\end{center}
% List datasets
We provide a range of data files to parameterise this problem. They are listed here with citations to the paper of origin.
\begin{itemize}
\itemsep0em
\item aiyoshi\_shimizu\_1984\_ex2~\cite[page 1114]{Aiyoshi1984}
\item an\_et\_al\_2009~\cite[page 332]{An2009}
\item bard\_1988\_ex1~\cite[page 18]{Bard1988}
\item bard\_1988\_ex2~\cite[page 23]{Bard1988}
\item bard\_1991\_ex1
\item bard\_book\_1998~\cite[page 326, Example 8.3.2]{Bard2000}
\item calamai\_vicente\_1994a~\cite[page 105]{Calamai1994}
\item calamai\_vicente\_1994b~\cite[page 115]{Calamai1994}
\item calamai\_vicente\_1994c~\cite[page 116]{Calamai1994}
\end{itemize}
classdef quadratic_bilevel
%{
Upper-level
===========
minimise 1/2 (x' P_upper x) + 1/2 (y' Q_upper y) + (x' R_upper y) + c_upper' x + d_upper' y
subject to A_upper * x + B_upper * y >= rhs_upper
x >= x_lower_bound
x <= x_upper_bound
y solves lower-level
Lower-level
===========
minimise 1/2 (x' P_lower x) + 1/2 (y' Q_lower y) + 1/2 (x' R_lower y) + c_lower' x + d_lower' y
subject to A_lower * x + B_lower * y >= rhs_lower
y >= y_lower_bound
y <= y_upper_bound
%}
properties(Constant)
name = 'quadratic_bilevel';
category = 'archetype';
subcategory = '';
datasets = {
'aiyoshi_shimizu_1984_ex2.json'; 'an_et_al_2009.json'; 'bard_1988_ex1.json';
'bard_1988_ex2.json'; 'bard_1991_ex1.json'; 'bard_book_1998.json';
'calamai_vicente_1994a.json'; 'calamai_vicente_1994b.json'; 'calamai_vicente_1994c.json';
'clark_westerberg_1990a.json'; 'dempe_etal_2012.json'; 'dempe_franke_2011_ex41.json';
'dempe_franke_2011_ex42.json'; 'dempe_franke_2014_ex38.json'; 'dempe_lohse_2011_ex31a.json';
'dempe_lohse_2011_ex31b.json'; 'desilva_1978.json'; 'falk_liu_1995.json';
'floudas_etal_2013.json'; 'gumus_floudas_2001_ex.json'; 'hatz_etal_2013.json';
'henderson_quandt_1958.json'; 'henrion_surowiec_2011.json'; 'lampariello_sagratella_2017_ex31.json';
'lampariello_sagratella_2017_ex32.json'; 'lampariello_sagratella_2017_ex33.json';
'lampariello_sagratella_2017_ex35.json'; 'lucchetti_etal_1987.json'; 'macal_hurter_1997.json';
'morgan_patrone_2006a.json'; 'muu_quy_2003_ex1.json'; 'muu_quy_2003_ex2.json';
'outrata_1990_ex1_a.json'; 'outrata_1990_ex1_b.json'; 'outrata_1990_ex1_c.json';
'outrata_1990_ex1_d.json'; 'outrata_1990_ex1_e.json'; 'outrata_cervinka_2009.json';
'sahin_ciric_1998_ex2.json'; 'shimizu_aiyoshi_1981_ex1.json'; 'shimizu_aiyoshi_1981_ex2.json';
'shimizu_etal_1997a.json'; 'sinha_malo_deb_2014_tp6.json'; 'tuy_etal_2007.json';
'wan_wang_lv_2011.json'; 'yezza_1996_ex3.json'; 'yezza_1996_ex4.json';
% Toll settings
'toll_setting_p1.json'; 'toll_setting_p2.json'; 'toll_setting_p3.json';
'toll_setting_p4.json'; 'toll_setting_p5.json';
};
paths = fullfile('bolib3', 'data', 'quadratic_bilevel', quadratic_bilevel.datasets);
x0 = [0.2; 2.0];
y0 = [4.0; 4.6];
required_data_fields = {
'n_x', 'n_y', ...
'A_upper', 'B_upper', 'c_upper', 'd_upper', 'rhs_upper', 'P_upper', 'Q_upper', 'R_upper', ...
'A_lower', 'B_lower', 'c_lower', 'd_lower', 'rhs_lower', 'P_lower', 'Q_lower', 'R_lower', ...
'x_upper_bound', 'x_lower_bound', ...
'y_upper_bound', 'y_lower_bound'
};
end
methods(Static)
% Upper-level objective function
% 1/2 (x' P_upper x) + 1/2 (y' Q_upper y) + (x' R_upper y) + c_upper' x + d_upper' y
function obj = F(x, y, data)
obj = 0.5 * x' * data.P_upper * x + ...
0.5 * y' * data.Q_upper * y + ...
1.0 * x' * data.R_upper * y + ...
dot(data.c_upper, x) + ...
dot(data.d_upper, y);
end
% Upper-level inequality constraints
% Ax + By >= rhs
% x >= x_lower_bound
% x <= x_upper_bound
function ineq = G(x, y, data)
ineq = [];
if ~isempty(data.rhs_upper)
ineq = [ineq; data.A_upper * x + data.B_upper * y - data.rhs_upper];
end
if ~isempty(data.x_lower_bound)
ineq = [ineq; x - data.x_lower_bound];
end
if ~isempty(data.x_upper_bound)
ineq = [ineq; data.x_upper_bound - x];
end
end
% Upper-level equality constraints
function val = H(~, ~, ~)
val = [];
end
% Lower-level objective function
% minimise f(x,y) := c'x + d'y
function obj = f(x, y, data)
obj = 0.5 * x' * data.P_lower * x +...
0.5 * y' * data.Q_lower * y +...
1.0 * x' * data.R_lower * y +...
dot(data.c_lower, x) +...
dot(data.d_lower, y);
end
% Lower-level inequality constraints
function ineq = g(x, y, data)
ineq = [];
if ~isempty(data.rhs_lower)
ineq = [ineq; data.A_lower * x + data.B_lower * y - data.rhs_lower];
end
if ~isempty(data.y_lower_bound)
ineq = [ineq; y - data.y_lower_bound];
end
if ~isempty(data.y_upper_bound)
ineq = [ineq; data.y_upper_bound - y];
end
end
% Lower-level equality constraints
function val = h(~, ~, ~)
val = [];
end
% If the bilevel program is parameterized by data, this function should
% provide code to read data file and return an appropriate structure.
function data = read_data(filepath)
% Read JSON file
file = fopen(filepath, 'r');
raw = fread(file, inf, 'uint8=>char')';
fclose(file);
data = jsondecode(raw);
% Add a field for the filepath
data.filepath = filepath;
% Bounds are optional. If they are not provided we replace them with an empty array
bounds = {'x_upper_bound', 'x_lower_bound', 'y_upper_bound', 'y_lower_bound'};
for i = 1:length(bounds)
if ~isfield(data, bounds{i})
data.(bounds{i}) = [];
end
end
% Validate required fields
for i = 1:length(quadratic_bilevel.required_data_fields)
key = quadratic_bilevel.required_data_fields{i};
assert(isfield(data, key), ...
sprintf("Missing required field '%s' in '%s'.", key, filepath));
end
end
% Key are the function/variable names
% Values are their dimention
function n = dimention(key, data)
n = dictionary( ...
'x', data.n_x, ...
'y', data.n_y, ...
'F', 1, ...
'G', length(data.rhs_upper) + length(data.x_upper_bound) + length(data.x_lower_bound), ...
'H', 0, ...
'f', 1, ...
'g', length(data.rhs_lower) + length(data.y_upper_bound) + length(data.y_lower_bound), ...
'h', 0 ...
);
if isKey(n,key)
n = n(key);
end
end
end
end
import json
import os.path
from bolib3 import np
"""
Quadratic Bilevel Program
Upper-level
===========
minimise 1/2 (x' P_upper x) + 1/2 (y' Q_upper y) + (x' R_upper y) + c_upper' x + d_upper' y
subject to A_upper * x + B_upper * y >= rhs_upper
x >= x_lower_bound
x <= x_upper_bound
y solves lower-level
Lower-level
===========
minimise 1/2 (x' P_lower x) + 1/2 (y' Q_lower y) + 1/2 (x' R_lower y) + c_lower' x + d_lower' y
subject to A_lower * x + B_lower * y >= rhs_lower
y >= y_lower_bound
y <= y_upper_bound
"""
# Properties
name: str = "quadratic_bilevel"
category: str = "archetype"
subcategory: str = ""
datasets: list = [
'aiyoshi_shimizu_1984_ex2.json', 'an_et_al_2009.json', 'bard_1988_ex1.json',
'bard_1988_ex2.json', 'bard_1991_ex1.json', 'bard_book_1998.json',
'calamai_vicente_1994a.json', 'calamai_vicente_1994b.json', 'calamai_vicente_1994c.json',
'clark_westerberg_1990a.json', 'dempe_etal_2012.json', 'dempe_franke_2011_ex41.json',
'dempe_franke_2011_ex42.json', 'dempe_franke_2014_ex38.json', 'dempe_lohse_2011_ex31a.json',
'dempe_lohse_2011_ex31b.json', 'desilva_1978.json', 'falk_liu_1995.json',
'floudas_etal_2013.json', 'gumus_floudas_2001_ex.json', 'hatz_etal_2013.json',
'henderson_quandt_1958.json', 'henrion_surowiec_2011.json', 'lampariello_sagratella_2017_ex31.json',
'lampariello_sagratella_2017_ex32.json', 'lampariello_sagratella_2017_ex33.json',
'lampariello_sagratella_2017_ex35.json', 'lucchetti_etal_1987.json', 'macal_hurter_1997.json',
'morgan_patrone_2006a.json', 'muu_quy_2003_ex1.json', 'muu_quy_2003_ex2.json',
'outrata_1990_ex1_a.json', 'outrata_1990_ex1_b.json', 'outrata_1990_ex1_c.json',
'outrata_1990_ex1_d.json', 'outrata_1990_ex1_e.json', 'outrata_cervinka_2009.json',
'sahin_ciric_1998_ex2.json', 'shimizu_aiyoshi_1981_ex1.json', 'shimizu_aiyoshi_1981_ex2.json',
'shimizu_etal_1997a.json', 'sinha_malo_deb_2014_tp6.json', 'tuy_etal_2007.json',
'wan_wang_lv_2011.json', 'yezza_1996_ex3.json', 'yezza_1996_ex4.json',
# Toll settings
'toll_setting_p1.json', 'toll_setting_p2.json', 'toll_setting_p3.json',
'toll_setting_p4.json', 'toll_setting_p5.json',
]
paths: list = [
os.path.join("bolib3", "data", "quadratic_bilevel", d) for d in datasets
]
# Feasible point
x0 = np.array([0.2, 2.0])
y0 = np.array([4.0, 4.6])
# When reading a json file containing the parameters for this problem the following fields must exits:
required_data_fields = (
# Dimensions
'n_x', 'n_y',
# Upper/lower-level matrices
'A_upper', 'B_upper', 'c_upper', 'd_upper', 'P_upper', 'Q_upper', 'R_upper', 'rhs_upper',
'A_lower', 'B_lower', 'c_lower', 'd_lower', 'P_lower', 'Q_lower', 'R_lower', 'rhs_lower',
# Bounds
'x_upper_bound', 'x_lower_bound',
'y_upper_bound', 'y_lower_bound',
)
# Methods
def F(x, y, data=None):
"""
Upper-level objective function (quadratic)
1/2 (x' P_upper x) + 1/2 (y' Q_upper y) + (x' R_upper y) + c_upper' x + d_upper' y
"""
return np.sum((
0.5*np.dot(x, np.dot(data['P_upper'], x)),
0.5*np.dot(y, np.dot(data['Q_upper'], y)),
1.0*np.dot(x, np.dot(data['R_upper'], y)),
np.dot(data['c_upper'], x),
np.dot(data['d_upper'], y)
))
def G(x, y, data=None):
"""
Upper-level inequality constraints (linear)
Ax + By >= rhs
x >= x_lower_bound
x <= x_upper_bound
"""
# Inequality constraints
ineq_list = [np.empty(0)]
if data['rhs_upper'].size:
ineq_list.append(np.matmul(data['A_upper'], x) + np.matmul(data['B_upper'], y) - data['rhs_upper'])
if data['x_lower_bound'].size:
ineq_list.append(x - data['x_lower_bound'])
if data['x_upper_bound'].size:
ineq_list.append(data['x_upper_bound'] - x)
# Constraints G(x, y) >= 0
return np.concatenate(ineq_list)
def H(x, y, data=None):
"""
Upper-level equality constraints (none)
"""
return np.empty(0)
def f(x, y, data=None):
"""
Lower-level objective function (quadratic)
1/2 (x' P_lower x) + 1/2 (y' Q_lower y) + (x' R_lower y) + c_lower' x + d_lower' y
"""
return np.sum((
0.5*np.dot(x, np.dot(data['P_lower'], x)),
0.5*np.dot(y, np.dot(data['Q_lower'], y)),
1.0*np.dot(x, np.dot(data['R_lower'], y)),
np.dot(data['c_lower'], x),
np.dot(data['d_lower'], y)
))
def g(x, y, data=None):
"""
Lower-level inequality constraints
Ax + By >= rhs
y >= y_lower_bound
y <= y_upper_bound
"""
# Inequality constraints
ineq_constraints = [np.empty(0)]
if data['rhs_lower'].size:
ineq_constraints.append(np.matmul(data['A_lower'], x) + np.matmul(data['B_lower'], y) - data['rhs_lower'])
if data['y_lower_bound'].size:
ineq_constraints.append(y - data['y_lower_bound'])
if data['y_upper_bound'].size:
ineq_constraints.append(data['y_upper_bound'] - y)
# Constraints g(x, y) >= 0
return np.concatenate(ineq_constraints)
def h(x, y, data=None):
"""
Lower-level equality constraints (none)
"""
return np.empty(0)
def read_data(filepath: str = datasets[0]):
"""
If the bilevel program is parameterized by data, this function should
provide code to read data file and return an appropriate python structure.
"""
with open(filepath, 'r') as f:
data = json.load(f)
# Add a field for the filepath
data['filepath'] = filepath
# Bounds are optional. If they are not provided we replace them with an empty array
for key in ['x_upper_bound', 'x_lower_bound', 'y_upper_bound', 'y_lower_bound']:
if (key not in data) or (not data[key]):
data[key] = []
# Validate required fields exist
for key in required_data_fields:
assert key in data, f"Missing required field {key} in '{filepath}'."
# Cast to numpy arrays
for key in set(required_data_fields) - {'n_x', 'n_y'}:
data[key] = np.array(data[key])
# Deal with empty arrays
for key, empty_shape in {
'A_upper': (0, data['n_x']), 'B_upper': (0, data['n_y']),
'A_lower': (0, data['n_x']), 'B_lower': (0, data['n_y'])
}.items():
if len(data[key]) == 0:
data[key] = np.empty(empty_shape)
# Validate dimension
validate_data_dimensions(data)
return data
def validate_data_dimensions(data: dict):
"""
See "Table of Dimensions" in the docstring at the top of this file.
"""
n_x = data['n_x']
n_y = data['n_y']
n_G = data['rhs_upper'].shape[0]
n_g = data['rhs_lower'].shape[0]
filepath = data['filepath']
for key, expected_shape in {
'A_upper': (n_G, n_x),
'B_upper': (n_G, n_y),
'c_upper': (n_x,),
'd_upper': (n_y,),
'P_upper': (n_x, n_x),
'Q_upper': (n_y, n_y),
'R_upper': (n_x, n_y),
'rhs_upper': (n_G,),
'A_lower': (n_g, n_x),
'B_lower': (n_g, n_y),
'c_lower': (n_x,),
'd_lower': (n_y,),
'P_lower': (n_x, n_x),
'Q_lower': (n_y, n_y),
'R_lower': (n_x, n_y),
'rhs_lower': (n_g,),
}.items():
assert data[key].shape == expected_shape, \
f"Dimension of {key} is {data[key].shape} but was expect to be {expected_shape}. Filepath: '{filepath}'."
def dimension(key='', data=None):
"""
If the argument 'key' is not specified, then:
- a dictionary mapping variable/function names (str) to the corresponding dimension (int) is returned.
If the first argument 'key' is specified, then:
- a single integer representing the dimension of the variable/function with the name {key} is returned.
"""
n = {
"x": data['n_x'],
"y": data['n_y'],
"F": 1,
"G": len(data['rhs_upper']) + len(data['x_upper_bound']) + len(data['x_lower_bound']),
"H": 0,
"f": 1,
"g": len(data['rhs_lower']) + len(data['y_upper_bound']) + len(data['y_lower_bound']),
"h": 0,
}
if key in n:
return n[key]
return n