Added 18/06/2025
Archetype
linear_bilevel
Datasets
Dimension
{
"x": 1,
"y": 1,
"F": 1,
"G": 1,
"H": 0,
"f": 1,
"g": 6,
"h": 0
}
Solution
{
"optimality": "global",
"x": [16],
"y": [11],
"F": -49,
"f": 17
}
Dimension
{
"x": 1,
"y": 1,
"F": 1,
"G": 1,
"H": 0,
"f": 1,
"g": 5,
"h": 0
}
Solution
{
"optimality": "global",
"x": [0.8888888888888888],
"y": [2.2222222222222223],
"F": 3.111111111111111,
"f": -6.666666666666667
}
Dimension
{
"x": 1,
"y": 1,
"F": 1,
"G": 1,
"H": 0,
"f": 1,
"g": 5,
"h": 0
}
Solution
{
"optimality": "best known",
"x": [7.2],
"y": [1.6],
"F": -37.6,
"f": 1.6
}
Dimension
{
"x": 1,
"y": 2,
"F": 1,
"G": 1,
"H": 0,
"f": 1,
"g": 5,
"h": 0
}
Solution
{
"optimality": "global",
"x": [0],
"y": [0,1],
"F": -1,
"f": -1
}
Dimension
{
"x": 2,
"y": 2,
"F": 1,
"G": 2,
"H": 0,
"f": 1,
"g": 5,
"h": 0
}
Solution
{
"optimality": "global",
"x": [2,0],
"y": [1.5,0],
"F": -3.25,
"f": -4
}
Dimension
{
"x": 1,
"y": 2,
"F": 1,
"G": 2,
"H": 0,
"f": 1,
"g": 4,
"h": 0
}
Solution
{
"optimality": "global",
"x": [1],
"y": [0,1],
"F": -2.5,
"f": -5
}
Dimension
{
"x": 1,
"y": 1,
"F": 1,
"G": 1,
"H": 0,
"f": 1,
"g": 4,
"h": 0
}
Solution
{
"optimality": "global",
"x": [1],
"y": [5],
"F": -6,
"f": 5
}
Dimension
{
"x": 1,
"y": 2,
"F": 1,
"G": 1,
"H": 0,
"f": 1,
"g": 7,
"h": 0
}
Solution
{
"optimality": "global",
"x": [1.5],
"y": [1,0.5],
"F": -2,
"f": -0.5
}
Dimension
{
"x": 1,
"y": 1,
"F": 1,
"G": 1,
"H": 0,
"f": 1,
"g": 6,
"h": 0
}
Solution
{
"optimality": "global",
"x": [16],
"y": [11],
"F": -11,
"f": 11
}
Dimension
{
"x": 2,
"y": 3,
"F": 1,
"G": 2,
"H": 0,
"f": 1,
"g": 6,
"h": 0
}
Solution
{
"optimality": "global",
"x": [0,0.9],
"y": [0,0.6,0.4],
"F": -29.2,
"f": 3.2
}
Dimension
{
"x": 1,
"y": 1,
"F": 1,
"G": 0,
"H": 0,
"f": 1,
"g": 3,
"h": 0
}
Solution
{
"optimality": "global",
"x": [19],
"y": [14],
"F": -37,
"f": 14
}
Dimension
{
"x": 1,
"y": 2,
"F": 1,
"G": 2,
"H": 0,
"f": 1,
"g": 5,
"h": 0
}
Solution
{
"optimality": "best known",
"x": [5],
"y": [4,2],
"F": -13,
"f": -4
}
Dimension
{
"x": 2,
"y": 1,
"F": 1,
"G": 3,
"H": 0,
"f": 1,
"g": 3,
"h": 0
}
Solution
{
"optimality": "global",
"x": [1,2],
"y": [0]
}
Dimension
{
"x": 1,
"y": 1,
"F": 1,
"G": 0,
"H": 0,
"f": 1,
"g": 4,
"h": 0
}
Solution
{
"optimality": "global",
"x": [12],
"y": [3],
"F": 27,
"f": -3
}
Dimension
{
"x": 1,
"y": 2,
"F": 1,
"G": 1,
"H": 0,
"f": 1,
"g": 5,
"h": 0
}
Solution
{
"optimality": "global",
"x": [1.8888888888888888],
"y": [0.8888888888888888,0],
"F": -8.444444444444445,
"f": -4.555555555555555
}
Dimension
{
"x": 10,
"y": 10,
"F": 1,
"G": 0,
"H": 0,
"f": 1,
"g": 11,
"h": 0
}
Solution
{
"optimality": "global",
"x": [1,1,1,1,1,1,1,1,1,1],
"y": [1,1,1,1,1,1,1,1,1,1],
"F": 10,
"f": 10
}
Dimension
{
"x": 100,
"y": 100,
"F": 1,
"G": 0,
"H": 0,
"f": 1,
"g": 101,
"h": 0
}
Solution
{
"optimality": "global",
"x": [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
"y": [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
"F": 100,
"f": 100
}
Dimension
{
"x": 3,
"y": 3,
"F": 1,
"G": 0,
"H": 0,
"f": 1,
"g": 4,
"h": 0
}
Solution
{
"optimality": "global",
"x": [1,1,1],
"y": [1,1,1],
"F": 3,
"f": 3
}
Dimension
{
"x": 50,
"y": 50,
"F": 1,
"G": 0,
"H": 0,
"f": 1,
"g": 51,
"h": 0
}
Solution
{
"optimality": "global",
"x": [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
"y": [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
"F": 50,
"f": 50
}
Dimension
{
"x": 1,
"y": 1,
"F": 1,
"G": 1,
"H": 0,
"f": 1,
"g": 7,
"h": 0
}
Solution
{
"optimality": "best known",
"x": [17.45],
"y": [10.908],
"F": -85.088,
"f": 50.174
}
Dimension
{
"x": 1,
"y": 1,
"F": 1,
"G": 1,
"H": 0,
"f": 1,
"g": 4,
"h": 0
}
Solution
{
"optimality": "global",
"x": [4],
"y": [4],
"F": -16,
"f": 4
}
Dimension
{
"x": 1,
"y": 1,
"F": 1,
"G": 1,
"H": 0,
"f": 1,
"g": 5,
"h": 0
}
Solution
{
"optimality": "best known",
"x": [9],
"y": [6],
"F": -39,
"f": 6
}
Dimension
{
"x": 1,
"y": 1,
"F": 1,
"G": 2,
"H": 0,
"f": 1,
"g": 2,
"h": 0
}
Solution
{
"optimality": "global",
"x": [8],
"y": [6],
"F": -20,
"f": -6
}
Dimension
{
"x": 2,
"y": 2,
"F": 1,
"G": 3,
"H": 0,
"f": 1,
"g": 4,
"h": 0
}
Solution
{
"optimality": "global",
"x": [2,0],
"y": [1.5,0],
"F": -3.25,
"f": -6
}
Dimension
{
"x": 2,
"y": 2,
"F": 1,
"G": 3,
"H": 0,
"f": 1,
"g": 3,
"h": 0
}
Solution
{
"optimality": "global",
"x": [0,3],
"y": [0,0],
"F": 6,
"f": 0
}
Dimension
{
"x": 10,
"y": 6,
"F": 1,
"G": 22,
"H": 0,
"f": 1,
"g": 19,
"h": 0
}
Solution
{
"optimality": "infeasible",
"x": [0,8.170692,10,0,7.27894,3.042311,0,10,0.001982,9.989153],
"y": [3.10128,10,10,10,0,9.846133],
"F": -467.461261,
"f": -11.619362
}
Dimension
{
"x": 1,
"y": 1,
"F": 1,
"G": 1,
"H": 0,
"f": 1,
"g": 5,
"h": 0
}
Solution
{
"optimality": "best known",
"x": [0.8888888888888888],
"y": [2.2222222222222223],
"F": 3.111111111111,
"f": -6.666666666666
}
$title linear_bilevel
$onText
Upper-level
============
minimise 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 c_lower ' x + d_lower ' y
subject to A_lower * x + B_lower * y <= rhs_lower
y >= y_lower_bound
y <= y_upper_bound
Table of Dimensions
===================
| Array | Shape |
| --------- | -------------- |
| A_upper | (n_upper, n_x) |
| B_upper | (n_upper, n_y) |
| c_upper | (n_x,) |
| d_upper | (n_y,) |
| rhs_upper | (n_upper,) |
| A_lower | (n_lower, n_x) |
| B_lower | (n_lower, n_y) |
| c_lower | (n_x,) |
| d_lower | (n_y,) |
| rhs_lower | (n_lower,) |
$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";
* 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"
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"
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/linear_bilevel_gdx/tuy_et_al_2007_ex3.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, rhs_upper=rhs_upper, x_lower_bound, x_upper_bound
$load A_lower=A_lower, B_lower=B_lower, c_lower=c_lower, d_lower=d_lower, rhs_lower=rhs_lower, 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= sum(i, c_upper(i)*x(i)) + sum(j, d_upper(j)*y(j));
* Lower-level objective
obj_eq_lower .. obj_val_lower =e= 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 linear_bilevel / all /;
$echo bilevel x min obj_val_lower y obj_eq_lower, lower_ineq > "%emp.info%"
solve linear_bilevel us emp min obj_val_upper;
\subsection{linear\_bilevel}
\label{subsec:linear_bilevel}
% Fully linear bilevel program
For decision variables $\x\in\R^{n_x}$ and $\y\in\R^{n_y}$ fully linear bilevel program has the form
\begin{flalign*}
\minimise_{\x\in\R^{n_x}, \y^*\in\R^{n_y}} \quad
& {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}
{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}$ \\
$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}$ \\
$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 20 data files to parametrise this problem. They are listed here with citations to the paper of origin.
\begin{itemize}
\itemsep0em
\item anandalingham\_white\_1990~\cite[page 1172]{anandalingham1990}
\item ben\_ayed\_blair\_1990a~\cite[page 557]{ben1990}
\item bialas\_karwan\_1984a~\cite[page 1009]{bialas1984}
\item bialas\_karwan\_1984b~\cite[page 1016]{bialas1984}
\item candler\_townsley\_1982~\cite[page 91]{candler1982}
\item clark\_westerberg\_1988~\cite{clark1988}
\item clark\_westerberg\_1990b~\cite[page 89]{clark1990}
\item glackin\_et\_al\_2009~\cite[page 206]{glackin2009}
\item haurie\_savard\_white\_1990~\cite{haurie1990}
\item hu\_huang\_zhang\_2009~\cite{hu2010}
\item lan\_wen\_shih\_lee\_2007~\cite{lan2007}
\item liu\_hart\_1994~\cite{liu1994}
\item mersha\_dempe\_2006\_ex1~\cite[page 5]{mersha2006}
\item mersha\_dempe\_2006\_ex2~\cite[page 7]{mersha2006}
\item tuy\_et\_al\_1993~\cite{tuy1993}
\item tuy\_et\_al\_1994~\cite{tuy1994}
\item tuy\_et\_al\_2007\_ex3~\cite[page 551]{tuy2007}
\item visweswaran\_et\_al\_1996~\cite{visweswaran1996}
\item wang\_jiao\_li\_2005~\cite{wang2005}
\end{itemize}
classdef linear_bilevel
%{
Upper-level
===========
minimise 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 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 = 'linear_bilevel';
category = 'archetype';
subcategory = '';
datasets = {
'anandalingham_white_1990.json'; 'bard_1984a.json'; 'bard_1984b.json'; 'bard_1991_ex2.json';
'bard_falk_1982_ex2.json'; 'ben_ayed_blair_1990a.json'; 'ben_ayed_blair_1990b.json';
'bialas_karwan_1984a.json'; 'bialas_karwan_1984b.json'; 'candler_townsley_1982.json';
'clark_westerberg_1988.json'; 'clark_westerberg_1990b.json'; 'glackin_et_al_2009.json';
'haurie_savard_white_1990.json'; 'hu_huang_zhang_2009.json'; 'hypercube_10.json'; 'hypercube_100.json';
'hypercube_3.json'; 'hypercube_50.json'; 'lan_wen_shih_lee_2007.json'; 'liu_hart_1994.json';
'mersha_dempe_2006_ex1.json'; 'mersha_dempe_2006_ex2.json';'tuy_et_al_1993.json'; 'tuy_et_al_1994.json';
'tuy_et_al_2007_ex3.json'; 'visweswaran_et_al_1996.json'; 'wang_jiao_li_2005.json'
};
paths = fullfile('bolib3', 'data', 'linear_bilevel', linear_bilevel.datasets);
x0 = [16.0];
y0 = [11.0];
required_data_fields = {
'n_x', 'n_y', ...
'A_upper', 'B_upper', 'c_upper', 'd_upper', 'rhs_upper', 'x_upper_bound', 'x_lower_bound', ...
'A_lower', 'B_lower', 'c_lower', 'd_lower', 'rhs_lower', 'y_upper_bound', 'y_lower_bound'
};
end
methods(Static)
% Upper-level objective function
% minimise F(x,y) := c'x + d'y
function obj = F(x, y, data)
obj = 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 = 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(linear_bilevel.required_data_fields)
key = linear_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
"""
Fully Linear Bilevel Program
Upper-level
===========
minimise 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 c_lower ' x + d_lower ' y
subject to A_lower * x + B_lower * y >= rhs_lower
y >= y_lower_bound
y <= y_upper_bound
Table of Dimensions
===================
| Array | Shape |
| --------- | ---------- |
| A_upper | (n_G, n_x) |
| B_upper | (n_G, n_y) |
| c_upper | (n_x,) |
| d_upper | (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,) |
| rhs_lower | (n_g,) |
"""
# Properties
name: str = "linear_bilevel"
category: str = "archetype"
subcategory: str = ""
datasets: list = [
'anandalingham_white_1990.json', 'bard_1984a.json', 'bard_1984b.json', 'bard_1991_ex2.json',
'bard_falk_1982_ex2.json', 'ben_ayed_blair_1990a.json', 'ben_ayed_blair_1990b.json', 'bialas_karwan_1984a.json',
'bialas_karwan_1984b.json', 'candler_townsley_1982.json', 'clark_westerberg_1988.json',
'clark_westerberg_1990b.json', 'glackin_et_al_2009.json', 'haurie_savard_white_1990.json',
'hu_huang_zhang_2009.json', 'hypercube_10.json', 'hypercube_100.json', 'hypercube_3.json', 'hypercube_50.json',
'lan_wen_shih_lee_2007.json', 'liu_hart_1994.json', 'mersha_dempe_2006_ex1.json', 'mersha_dempe_2006_ex2.json',
'tuy_et_al_1993.json', 'tuy_et_al_1994.json','tuy_et_al_2007_ex3.json', 'visweswaran_et_al_1996.json',
'wang_jiao_li_2005.json'
]
paths: list = [
os.path.join('bolib3', 'data', 'linear_bilevel', dataset) for dataset in datasets
]
# Feasible point
x0 = np.array([16.0])
y0 = np.array([11.0])
# When reading a json file containing the parameters for this problem the following fields must exits:
required_data_fields = (
'n_x', 'n_y', # Dimensions
'A_upper', 'B_upper', 'c_upper', 'd_upper', 'rhs_upper', 'x_upper_bound', 'x_lower_bound', # Upper-level
'A_lower', 'B_lower', 'c_lower', 'd_lower', 'rhs_lower', 'y_upper_bound', 'y_lower_bound', # Lower-level
)
# Methods
def F(x, y, data=None):
"""
Upper-level objective function
minimise F(x,y) := c'x + d'y
"""
c_upper = data['c_upper']
d_upper = data['d_upper']
return np.dot(c_upper, x) + np.dot(d_upper, y)
def G(x, y, data=None):
"""
Upper-level inequality constraints
Ax + By >= rhs
x >= x_lower_bound
x <= x_upper_bound
"""
# Model parameters
A_upper = data['A_upper']
B_upper = data['B_upper']
rhs_upper = data['rhs_upper']
x_upper_bound = data['x_upper_bound']
x_lower_bound = data['x_lower_bound']
# Inequality constraints
ineq_list = [np.empty(0)]
if rhs_upper.size:
ineq_list.append(np.matmul(A_upper, x) + np.matmul(B_upper, y) - rhs_upper)
if x_lower_bound.size:
ineq_list.append(x - x_lower_bound)
if x_upper_bound.size:
ineq_list.append(x_upper_bound - x)
# Constraints G(x, y) >= 0
return np.concatenate(ineq_list)
def H(x, y, data=None):
"""
Upper-level equality constraints
"""
return np.empty(0)
def f(x, y, data=None):
"""
Lower-level objective function
minimise f(x,y) := c'x + d'y
"""
c_lower = data['c_lower']
d_lower = data['d_lower']
return np.dot(c_lower, x) + np.dot(d_lower, y)
def g(x, y, data=None):
"""
Lower-level inequality constraints
Ax + By >= rhs
y >= y_lower_bound
y <= y_upper_bound
"""
# Model parameters
A_lower = data['A_lower']
B_lower = data['B_lower']
rhs_lower = data['rhs_lower']
y_upper_bound = data['y_upper_bound']
y_lower_bound = data['y_lower_bound']
# Inequality constraints
ineq_constraints = [np.empty(0)]
if rhs_lower.size:
ineq_constraints.append(np.matmul(A_lower, x) + np.matmul(B_lower, y) - rhs_lower)
if y_lower_bound.size:
ineq_constraints.append(y - y_lower_bound)
if y_upper_bound.size:
ineq_constraints.append(y_upper_bound - y)
# Constraints g(x, y) >= 0
return np.concatenate(ineq_constraints)
def h(x, y, data=None):
"""
Lower-level equality constraints
"""
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
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 filed {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']
# Dimension n_x
for key in ('A_upper', 'c_upper', 'A_lower', 'c_lower'):
assert data[key].shape[-1] == n_x, \
f"Dimension of {key} is {data[key].shape} but it should match n_x: {n_x}. Filepath: '{filepath}'."
# Dimension n_y
for key in ('B_upper', 'd_upper', 'B_lower', 'd_lower'):
assert data[key].shape[-1] == n_y, \
f"Dimension of {key} is {data[key].shape} but it should match n_y: {n_y}. Filepath: '{filepath}'."
# Dimension m_G
for key in ('A_upper', 'B_upper'):
assert data[key].shape[0] == n_G, \
f"Dimension of {key} is {data[key].shape} but it should match rhs_upper: {n_G}. Filepath: '{filepath}'."
# Dimension m_g
for key in ('A_lower', 'B_lower'):
assert data[key].shape[0] == n_g, \
f"Dimension of {key} is {data[key].shape} but it should match rhs_lower: {n_g}. Filepath: '{filepath}'."
# Dimension x bounds
for key in ('x_lower_bound', 'x_upper_bound'):
assert data[key].size in (0, n_x), \
f"Dimension of {key} is {data[key].shape} but it should match n_x: {n_x}. Filepath: '{filepath}'."
# Dimension y bounds
for key in ('y_lower_bound', 'y_upper_bound'):
assert data[key].size in (0, n_y), \
f"Dimension of {key} is {data[key].shape} but it should match n_y: {n_y}. 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