Added 18/06/2025
Textbook / bard_1998
bard721
Dimension
{
"x": 2,
"y": 1,
"F": 1,
"G": 4,
"H": 0,
"f": 1,
"g": 2,
"h": 0
}Solution
{
"optimality": "global",
"x": [0.8, 0.2],
"y": [0],
"F": 0.5,
"G": [0.8, 0.2, 0.2, 0.8],
"H": [],
"f": 0,
"g": [0, 1],
"h": []
}$title Practical Bilevel Optimization Example 7.2.1 (BARD721,SEQ=5)
$onText
Example from Chapter 7, example 7.2.1, page 275
John F. Bard, Practical Bilevel Optimization: Algorithms and Applications,
Kluwer Academic Publishers, Dordrecht, 1998.
Contributor: Jan-H. Jagla, January 2009
$offText
positive variables x1,x2,y; variables objout,objin;
equations defout,defin;
defout.. objout =e= 1/2*sqr(x1-4/5) + 1/2*sqr(x2-1/5) + 1/2*sqr(y-1);
defin.. objin =e= 1/2*sqr(y) - y - x1*y + 2*x2*y;
x1.up = 1; x2.up=1; y.up = 1;
model bard / all /;
$echo bilevel x1 x2 min objin y defin > "%emp.info%"
solve bard us emp min objout;
*Note: The subsolver used by EMP might not find the global solution
parameter solution(*,*);
solution('x1','book') = 0.8; solution('x1','model') = x1.l;
solution('x2','book') = 0.2; solution('x2','model') = x2.l;
solution('y' ,'book') = 1 ; solution('y' ,'model') = y.l;
display solution;\subsection{bard721}
\label{subsec:bard721}
% Description: bard721
This is a three-variable quadratic bilevel programming problem from~\cite[Chapter 7, example 7.2.1, page 275]{Bard2000}.
It has a solution at $(x_1, x_2, y)=(0.8, 0.2, 1)$.
% Equation: bard721
\begin{align*}
&\minimise_{x_1, x_2, y} \quad
&& \frac{1}{2}\left(x_1 - \frac{4}{5}\right)^2 +
\frac{1}{2}\left(x_2 - \frac{1}{5}\right)^2 +
\frac{1}{2}\left(y - 1 \right)^2
\\
&\subjectto
&& 0 \leq x_1 \leq 1, \\
&&& 0 \leq x_2 \leq 1, \\
&&& y \in \argmin_{y}
\left\{
\begin{aligned}
& \frac{1}{2}y^2 + y - x_1 y + 2x_2 y,\\
& \subjectto\quad 0 \leq y \leq 1.
\end{aligned}
\right.
\end{align*}classdef bard721
%{
Reference
John F. Bard
Practical Bilevel Optimization: Algorithms and Applications
Chapter 7, example 7.2.1, page 275
%}
properties(Constant)
name = 'bard721';
category = 'textbook';
subcategory = 'bard_1998';
datasets = {};
x0 = [0.8, 0.2];
y0 = [0.0];
end
methods(Static)
% Upper-level objective function (quadratic)
function val = F(x, y, ~)
val = 0.5*(x(1) - 0.8)^2 + 0.5*(x(2) - 0.2)^2 + 0.5*(y(1) - 1.0)^2;
end
% Upper-level inequality constraints (bounds)
function val = G(x, ~, ~)
val = [x(1); x(2); 1-x(1); 1-x(2)];
end
% Upper-level equality constraints (none)
function val = H(~, ~, ~)
val = [];
end
% Lower-level objective function (quadratic)
function val = f(x, y, ~)
val = 0.5*y(1)^2 + y(1) - x(1)*y(1) + 2*x(2)*y(1);
end
% Lower-level inequality constraints (bounds)
function val = g(~, y, ~)
val = [y(1); 1-y(1)];
end
% Lower-level equality constraints (none)
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 val = read_data(~)
val = [];
end
% Key are the function/variable names
% Values are their dimention
function n = dimentions(key, ~)
n = dictionary( ...
'x', 2, ...
'y', 1, ...
'F', 1, ...
'G', 4, ...
'H', 0, ...
'f', 1, ...
'g', 2, ...
'h', 0 ...
);
if isKey(n,key)
n = n(key);
end
end
end
endfrom bolib3 import np
"""
Reference
John F. Bard
Practical Bilevel Optimization: Algorithms and Applications
Chapter 7, example 7.2.1, page 275
"""
# Properties
name: str = 'bard721'
category: str = 'textbook'
subcategory: str = 'bard_1998'
datasets: list = []
# Feasible point
x0 = np.array([0.8, 0.2])
y0 = np.array([0.0])
# Methods
def F(x, y, data=None):
"""
Upper-level objective function
(quadratic)
"""
return 0.5*(x[0] - 0.8)**2 + 0.5*(x[1] - 0.2)**2 + 0.5*(y[0] - 1.0)**2
def G(x, y, data=None):
"""
Upper-level inequality constraints
(bounds)
"""
return np.array([
x[0],
x[1],
1-x[0],
1-x[1]
])
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)
"""
return 0.5*y[0]**2 + y[0] - x[0]*y[0] + 2*x[1]*y[0]
def g(x, y, data=None):
"""
Lower-level inequality constraints
(bounds)
0 <= y <= 1
"""
return np.array([
y[0],
1-y[0]
])
def h(x, y, data=None):
"""
Lower-level equality constraints
(none)
"""
return np.empty(0)
def read_data(filepath=''):
"""
If the bilevel program is parameterized by data, this function should
provide code to read data file and return an appropriate python structure.
"""
pass
def dimensions(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": 2, # Upper-level variables
"y": 1, # Lower-level variables
"F": 1, # Upper-level objective functions
"G": 4, # Upper-level inequality constraints
"H": 0, # Upper-level equality constraints
"f": 1, # Lower-level objective functions
"g": 2, # Lower-level inequality constraints
"h": 0 # Lower-level equality constraints
}
if key in n:
return n[key]
return n