Added 18/06/2025
Archetype
quadratic_bilevel
Datasets
Description
Aiyoshi, E. and Shimizu, K. (1984) (see page 1114).
A solution method for the static constrained Stackelberg problem via penalty method.
https://doi.org/10.1109/TAC.1984.1103455Dimension
{
"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": 5,
"G": [0,25,30,25,20],
"H": [],
"f": 0,
"g": [5,0,15,20,15,10],
"h": []
}Description
Hoai An, Le Thi and Tao, Pham Dinh and Nguyen Canh, Nam and Thoai, Nguyen (2009) (see page 332).
DC programming techniques for solving a class of nonlinear bilevel programs.
https://doi.org/10.1007/s10898-008-9325-7Dimension
{
"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": [1.6000711866581696e-10,-1.4000245407430612e-10,0.2,2],
"H": [],
"f": 565.774477,
"g": [2.000177801164682e-11,7.105427357601002e-15,3.998934516857844e-11,3.800018077981804e-10,4,4.6],
"h": []
}Description
Bard, Jonathan F. (1988) (see page 18).
Convex two-level optimization.
https://doi.org/10.1007/BF01580720Dimension
{
"x": 1,
"y": 1,
"F": 1,
"G": 1,
"H": 0,
"f": 1,
"g": 4,
"h": 0
}Solution
{
"optimality": "global",
"x": [1],
"y": [0],
"F": 17,
"G": [1],
"H": [],
"f": 1,
"g": [0,3,6,0],
"h": []
}Description
Bard, Jonathan F. (1988) (see page 23).
Convex two-level optimization.
https://doi.org/10.1007/BF01580720Dimension
{
"x": 4,
"y": 4,
"F": 1,
"G": 9,
"H": 0,
"f": 1,
"g": 12,
"h": 0
}Solution
{
"optimality": "unknown",
"F": -6600,
"f": 54
}Description
Bard, Jonathan F. (1991) (see page 373).
Some properties of the bilevel programming problem.
https://doi.org/10.1007/BF00941574Dimension
{
"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],
"H": [],
"f": 12,
"g": [0,6,0],
"h": []
}Description
Bard, Jonathan F. (1998) (see page 326, example 8.3.2).
Practical Bilevel Optimization: Algorithms And Applications.
https://doi.org/10.1007/978-1-4757-2836-1Dimension
{
"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": 0,
"G": [25,30,25,20],
"H": [],
"f": 5,
"g": [0,5,0,15,20,15,10],
"h": []
}Description
Calamai, Paul H. and Vicente, Luis N. (1994).
Generating quadratic bilevel programming test problems.
https://doi.org/10.1145/174603.174411Dimension
{
"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.0625,
"G": [],
"H": [],
"f": -0.1875,
"g": [0,0.5,0],
"h": []
}Description
Calamai, Paul H. and Vicente, Luis N. (1994) (see page 115).
Generating quadratic bilevel programming test problems.
https://doi.org/10.1145/174603.174411Dimension
{
"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": 0.3125,
"G": [],
"H": [],
"f": -0.40625,
"g": [0,1,0,2,0.5,0],
"h": []
}Description
Calamai, Paul H. and Vicente, Luis N. (1994) (see page 116).
Generating quadratic bilevel programming test problems.
https://doi.org/10.1145/174603.174411Dimension
{
"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": 0.3125,
"G": [],
"H": [],
"f": -0.40625,
"g": [0,1,0,2,0.5,-1.1102230246251565e-16],
"h": []
}Description
Paulavicius, Remigijus and Adjiman, Claire S. (2017).
BASBLib - a library of bilevel test problems.
https://doi.org/10.5281/zenodo.897966Dimension
{
"x": 1,
"y": 1,
"F": 1,
"G": 2,
"H": 0,
"f": 1,
"g": 3,
"h": 0
}Solution
{
"optimality": "global",
"x": [1],
"y": [3],
"F": 5,
"G": [7,1],
"H": [],
"f": 4,
"g": [0,3,7],
"h": []
}Description
Dempe, S. and Mordukhovich, B. S. and Zemkoho, A. B. (2012).
Sensitivity Analysis for Two-Level Value Functions with Applications to Bilevel Programming.
https://doi.org/10.1137/110845197Dimension
{
"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],
"H": [],
"f": -1,
"g": [1,0],
"h": []
}Description
Dempe, Stephan and Franke, Susanne (2011).
An algorithm for solving a class of bilevel programming problems.
https://tu-freiberg.de/fakult1/forschung/preprintsDimension
{
"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,0],
"H": [],
"f": -2,
"g": [0,1,0,2],
"h": []
}Description
Dempe, Stephan and Franke, Susanne (2011).
An algorithm for solving a class of bilevel programming problems.
https://tu-freiberg.de/fakult1/forschung/preprintsDimension
{
"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": 3,
"G": [2,0,0,0],
"H": [],
"f": -1,
"g": [0,2.5,1],
"h": []
}Description
Dempe, Stephan and Franke, Susanne (2014) (see page 279).
Solution algorithm for an optimistic linear Stackelberg problem.
https://doi.org/10.1016/j.cor.2012.09.002Dimension
{
"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],
"H": [],
"f": -4,
"g": [2,2,0,0],
"h": []
}Description
Dempe, Stephan and Lohse, Sebastian (2011).
Dependence of bilevel programming on irrelevant data.
https://optimization-online.org/2011/05/3038/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": -5.5,
"G": [],
"H": [],
"f": 0,
"g": [0,0,1,1],
"h": []
}Description
Dempe, Stephan and Lohse, Sebastian (2011).
Dependence of bilevel programming on irrelevant data.
https://optimization-online.org/2011/05/3038/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,
"G": [],
"H": [],
"f": 0,
"g": [0,0,0,0,2],
"h": []
}Description
De Silva, A. H. (1978).
Sensitivity formulas for nonlinear factorable programming and their application to the solution of an implicitly defined optimization model of US crude oil production.
https://wrlc-gwu.primo.exlibrisgroup.com/permalink/01WRLC_GWA/1j51gk4/alma9925067753604107Dimension
{
"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": [],
"H": [],
"f": 0,
"g": [0,0,1,1],
"h": []
}Description
Falk, James E and Liu, Jiming (1995).
On bilevel programming, Part {I}: general nonlinear cases.
https://doi.org/10.1007/BF01585928Dimension
{
"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": [],
"H": [],
"f": 0,
"g": [0.3660254037844386,0.3660254037844386,0.6339745962155614,0.6339745962155614],
"h": []
}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": 0,
"G": [0,0,50,50],
"H": [],
"f": 200,
"g": [10,10,30,0,0,30,30],
"h": []
}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": 9,
"G": [2,5,1,3,5],
"H": [],
"f": 0,
"g": [5,5],
"h": []
}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": [],
"H": [],
"f": 0,
"g": [0,0],
"h": []
}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],
"H": [],
"f": -711.1111111555551,
"g": [26.66666667],
"h": []
}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": [],
"H": [],
"f": -0.125,
"g": [],
"h": []
}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],
"H": [],
"f": 0,
"g": [0],
"h": []
}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": [],
"H": [],
"f": 0,
"g": [],
"h": []
}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],
"H": [],
"f": 0.5,
"g": [0,0.5,0],
"h": []
}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.19999999999999996],
"H": [],
"f": -0.4,
"g": [0,0.4,0.6],
"h": []
}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,
"G": [1,0],
"H": [],
"f": 0,
"g": [0,1],
"h": []
}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": 81.32617377999999,
"G": [],
"H": [],
"f": -0.3321014549999859,
"g": [],
"h": []
}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],
"H": [],
"f": 0,
"g": [2,0],
"h": []
}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],
"H": [],
"f": -0.5862964900000003,
"g": [1.1562,0.7657,0],
"h": []
}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],
"H": [],
"f": 1.670792,
"g": [0.001000000000000334,0,0,1.828],
"h": []
}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": [],
"H": [],
"f": -6.053999999999999,
"g": [1.0658,-0.0005999999999999339,2.6,1.8],
"h": []
}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": [],
"H": [],
"f": -0.5799499999999999,
"g": [1.74922,0.002990000000000048,2.34,1.03],
"h": []
}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": [],
"H": [],
"f": -112.71000000000001,
"g": [-0.0009999999999998899,-0.0009999999999998899,3,3],
"h": []
}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": [],
"H": [],
"f": -2,
"g": [2.666,0,2,0],
"h": []
}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": [],
"H": [],
"f": -16.2898,
"g": [0.41999999999999993,2.52614,0,1.58],
"h": []
}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],
"H": [],
"f": 0,
"g": [0,0,0],
"h": []
}Dimension
{
"x": 16,
"y": 24,
"F": 1,
"G": 0,
"H": 0,
"f": 1,
"g": 48,
"h": 0
}Solution
{
"optimality": "global",
"F": -6.4375,
"G": [],
"H": [],
"f": -1.83125,
"h": []
}Dimension
{
"x": 27,
"y": 27,
"F": 1,
"G": 0,
"H": 0,
"f": 1,
"g": 81,
"h": 0
}Solution
{
"optimality": "global",
"F": -10.585,
"G": [],
"H": [],
"f": -3.5575,
"h": []
}Dimension
{
"x": 2,
"y": 3,
"F": 1,
"G": 0,
"H": 0,
"f": 1,
"g": 6,
"h": 0
}Solution
{
"optimality": "global",
"x": [3.9742278313,3.9782225338],
"y": [-0.027203195,0.3097880937,-0.1390405894],
"F": -0.7975,
"G": [],
"H": [],
"f": -0.55125,
"g": [-4.261924146931051e-11,7.944158664230372e-10,3.0957691965483036e-10,9.474374618179127e-10,-3.0957691965483036e-10,0.8999999990525624],
"h": []
}Dimension
{
"x": 32,
"y": 48,
"F": 1,
"G": 0,
"H": 0,
"f": 1,
"g": 96,
"h": 0
}Solution
{
"optimality": "global",
"F": -12.7625,
"G": [],
"H": [],
"f": -3.46875,
"h": []
}Dimension
{
"x": 3,
"y": 3,
"F": 1,
"G": 0,
"H": 0,
"f": 1,
"g": 9,
"h": 0
}Solution
{
"optimality": "global",
"x": [1,1.45,0.5],
"y": [0,0.45,0.5],
"F": -1.0475,
"G": [],
"H": [],
"f": -0.67625,
"g": [0,0,1,0,0,1.7000000000000002,0,0.8999999999999999,0],
"h": []
}Dimension
{
"x": 4,
"y": 6,
"F": 1,
"G": 0,
"H": 0,
"f": 1,
"g": 12,
"h": 0
}Solution
{
"optimality": "global",
"x": [0.7632918515,0.5902695267,-0.4922192531,0.1200190564],
"y": [0.0492924285,0.5446286519,0.5665966409,0.3371019339,0,0.2143487178],
"F": -1.41,
"G": [],
"H": [],
"f": -0.595,
"h": []
}Dimension
{
"x": 8,
"y": 12,
"F": 1,
"G": 0,
"H": 0,
"f": 1,
"g": 24,
"h": 0
}Solution
{
"optimality": "global",
"x": [1.8624924073,0.4872349406,0.5665966409,0.7054834322,0.3123541324,0.3676631693,0.6842157921,0.6192019434],
"F": -3.235,
"G": [],
"H": [],
"f": -0.5825,
"h": []
}Dimension
{
"x": 9,
"y": 9,
"F": 1,
"G": 0,
"H": 0,
"f": 1,
"g": 27,
"h": 0
}Solution
{
"optimality": "global",
"x": [1.1,1.05,0.5,1,0.5,0.5,1.05,1,1],
"y": [0.1,0.05,0.5,0,0.5,0.5,0.05,0,0],
"F": -3.735,
"G": [],
"H": [],
"f": -0.5825,
"h": []
}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": 5,
"G": [1,7],
"H": [],
"f": 4,
"g": [0,3,7],
"h": []
}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": 100,
"G": [0,10,5],
"H": [],
"f": 0,
"g": [0,10,10],
"h": []
}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": 225,
"G": [0,0,10],
"H": [],
"f": 100,
"g": [10,5,0,5],
"h": []
}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": 25,
"G": [],
"H": [],
"f": -14,
"g": [10,0,0],
"h": []
}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": 1,
"G": [0],
"H": [],
"f": 17,
"g": [12,-4,4,4,0,0],
"h": []
}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],
"H": [],
"f": 12,
"h": []
}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],
"F": -4.5,
"G": [0.5,4,4.5],
"H": [],
"f": 32,
"h": []
}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],
"F": -3.5,
"G": [5,3.5,8.5],
"H": [],
"f": 32,
"h": []
}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": [],
"H": [],
"f": 14,
"g": [0,0,0,0,0,1,1,0],
"h": []
}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": [],
"H": [],
"f": 14,
"g": [0,0,0,0,0,1,0,1],
"h": []
}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],
"H": [],
"f": -1.523438,
"g": [-0.000002000000000279556,0.9843740000000007,5.9374980000000015],
"h": []
}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": 10.625,
"G": [],
"H": [],
"f": -0.5,
"g": [0.5,0,0,0,0.75,0,0.5,0],
"h": []
}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": 1.5,
"G": [0.25,0.75],
"H": [],
"f": -2.5,
"g": [0,1],
"h": []
}$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 using emp min obj_val_upper;
\subsection{quadratic\_bilevel}
\label{subsec:quadratic_bilevel}
% Quadratic bilevel program
For decision variables $\x\in\R^{n_x}$, $\y\in\R^{n_y}$, the \emph{Quadratic Bilevel Program}~\eqref{eq:QBP} is defined as:
\begin{flalign*}
\label{eq:QBP}
\tag{QBP}
\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^\top_\upper} \x
+ {d^\top_\upper} \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\{\mkern-10mu
\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^\top_\low} \x
+ {d^\top_\low} \y\\
\st[1]\quad {A_\low} \x + {B_\low} \y \geq {r_\low},\\
\st[2]\quad \ylb\leq \y \leq\yub.
\end{array}
\right.
\end{flalign*}
where the program is parametrised by the coefficients in Table~\ref{tab:parameters_QBP}.
% //==================================================\\
% || Table: Parameters of Quadratic Bilevel ||
% \\==================================================//
\begin{table}[H]
\centering
\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}
\caption{Parameters of the~\eqref{eq:QBP}}
\label{tab:parameters_QBP}
\end{table}classdef quadratic_bilevel
% Quadratic Bilevel Program (QBP)
% ===============================
% The QBP has a quadratic objective function and linear constraints in both the upper and lower level.
% The coefficients are stored in matrix form in the folder bolib3/data/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
%
%
% 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,) |
% | 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,) |
% were n_x and n_y are the number of upper-level and lower-level decision variables respectively.
% and n_G and n_g are the number of upper-level and lower-level inequality constraints respectively.
%
%
% Example MATLAB use case
% =======================
% addpath('bolib3/matlab');
% data = quadratic_bilevel.read_data('bolib3/data/quadratic_bilevel/aiyoshi_shimizu_1984_ex2.json');
% x = [25.0; 30.0];
% y = [5.0; 10.0];
% linear_bilevel.g(x, y, data)
properties(Constant)
name = 'quadratic_bilevel';
category = 'archetype';
subcategory = '';
author = 'Samuel Ward';
datasets = sort({
'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_ex4.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'; 'qbp_16_24.json'; 'qbp_27_27.json'; 'qbp_2_3.json';
'qbp_32_48.json'; 'qbp_3_3.json'; 'qbp_4_6.json'; 'qbp_8_12.json'; 'qbp_9_9.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'; 'toll_setting_p1.json'; 'toll_setting_p2.json'; 'toll_setting_p3.json';
'toll_setting_p4.json'; 'toll_setting_p5.json'; 'tuy_etal_2007.json'; 'wan_wang_lv_2011.json';
'yezza_1996_ex3.json'; 'yezza_1996_ex4.json'
});
paths = fullfile('bolib3', 'data', 'quadratic_bilevel', quadratic_bilevel.datasets);
end
methods(Static)
function obj = F(x, y, data)
% Upper-level objective function
% minimise F(x,y) := 1/2 (x'Px) + 1/2 (y'Qy) + (x'Ry) + c'x + d'y
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) + ...
data.s_upper;
end
function ineq = G(x, y, data)
% Upper-level inequality constraints
% Ax + By >= rhs
% x >= x_lower_bound
% x <= x_upper_bound
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
function val = H(~, ~, ~)
% Upper-level equality constraints
val = [];
end
function obj = f(x, y, data)
% Lower-level objective function
% minimise f(x,y) := 1/2 (x'Px) + 1/2 (y'Qy) + (x'Ry) + c'x + d'y
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) + ...
data.s_lower;
end
function ineq = g(x, y, data)
% Lower-level inequality constraints
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
function val = h(~, ~, ~)
% Lower-level equality constraints
val = [];
end
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %
% -=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=- %
%% Derivatives %%
% -=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=- %
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %
function dx = dF_dx(x, y, data)
% ∂F/∂x
% Dimention (n_x × 1)
dx = (data.P_upper * x) + (data.R_upper * y) + data.c_upper;
end
function dy = dF_dy(x, y, data)
% ∂F/∂y
% Dimention (n_y × 1)
dy = (data.Q_upper * y) + (data.R_upper' * x) + data.d_upper;
end
function Hxx = d2F_dxx(~, ~, data)
% ∂²F/∂x²
% Dimention (n_x × n_x)
Hxx = data.P_upper;
end
function Hyy = d2F_dyy(~, ~, data)
% ∂²F/∂y²
% Dimention (n_y × n_y)
Hyy = data.Q_upper;
end
function Hxy = d2F_dxy(~, ~, data)
% ∂²F/∂x∂y
% Dimention (n_x × n_y)
Hxy = data.R_upper;
end
function Jx = dG_dx(~, ~, data)
% Jacobian of G wrt x
% Dimention (|G| × n_x)
Jx = zeros(0, data.n_x);
if ~isempty(data.rhs_upper)
Jx = [Jx; data.A_upper];
end
if ~isempty(data.x_lower_bound)
Jx = [Jx; eye(data.n_x)];
end
if ~isempty(data.x_upper_bound)
Jx = [Jx; -eye(data.n_x)];
end
end
function Jy = dG_dy(~, ~, data)
% Jacobian of G wrt y:
% Dimention (|G| × n_y)
Jy = zeros(0, data.n_y);
if ~isempty(data.rhs_upper)
Jy = [Jy; data.B_upper];
end
if ~isempty(data.x_lower_bound)
Jy = [Jy; zeros(data.n_x, data.n_y)];
end
if ~isempty(data.x_upper_bound)
Jy = [Jy; zeros(data.n_x, data.n_y)];
end
end
function Jx = dH_dx(~, ~, data)
% Jacobian of H wrt x
% Dimention (0 × n_x)
Jx = zeros(0, data.n_x);
end
function Jy = dH_dy(~, ~, data)
% Jacobian of H wrt y
% Dimention (0 × n_y)
Jy = zeros(0, data.n_y);
end
function dx = df_dx(x, y, data)
% ∂f/∂x
% Dimention (n_x × 1)
dx = (data.P_lower * x) + (data.R_lower * y) + data.c_lower;
end
function dy = df_dy(x, y, data)
% ∂f/∂y
% Dimention (n_y × 1)
dy = (data.Q_lower * y) + (data.R_lower' * x) + data.d_lower;
end
function Hxx = d2f_dxx(~, ~, data)
% ∂²f/∂x²
% Dimention (n_x × n_x)
Hxx = data.P_lower;
end
function Hyy = d2f_dyy(~, ~, data)
% ∂²f/∂y²
% Dimention (n_y × n_y)
Hyy = data.Q_lower;
end
function Hxy = d2f_dxy(~, ~, data)
% ∂²f/∂x∂y
% Dimention (n_x × n_y)
Hxy = data.R_lower;
end
function Jx = dg_dx(~, ~, data)
% Jacobian of g wrt x
% Dimention (|g| × n_x)
Jx = zeros(0, data.n_x);
if ~isempty(data.rhs_lower)
Jx = [Jx; data.A_lower];
end
if ~isempty(data.y_lower_bound)
Jx = [Jx; zeros(data.n_y, data.n_x)];
end
if ~isempty(data.y_upper_bound)
Jx = [Jx; zeros(data.n_y, data.n_x)];
end
end
function Jy = dg_dy(~, ~, data)
% Jacobian of g wrt y
% Dimention (|g| × n_y)
Jy = zeros(0, data.n_y);
if ~isempty(data.rhs_lower)
Jy = [Jy; data.B_lower];
end
if ~isempty(data.y_lower_bound)
Jy = [Jy; eye(data.n_y)];
end
if ~isempty(data.y_upper_bound)
Jy = [Jy; -eye(data.n_y)];
end
end
function Jx = dh_dx(~, ~, data)
% Jacobian of h wrt x
% Dimention (0 × n_x)
Jx = zeros(0, data.n_x);
end
function Jy = dh_dy(~, ~, data)
% Jacobian of h wrt y
% Dimention (0 × n_y)
Jy = zeros(0, data.n_y);
end
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %
% -=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=- %
%% Read Data %%
% -=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=- %
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %
function data = read_data(path)
% Read JSON file
txt = fileread(path);
data = jsondecode(txt);
% Store the path. This is useful diagnostics
data.path = char(path);
% ================== REQUIRED keys ==================
% Dimensions and objective coefficients are nessasary
keys = {
'n_x', 'n_y', ...
'c_upper', 'd_upper', 'P_upper', 'Q_upper', 'R_upper', ...
'c_lower', 'd_lower', 'P_lower', 'Q_lower', 'R_lower', ...
};
for i = 1:length(keys)
key = keys{i};
msg = sprintf('Missing required key "%s". See JSON file: %s.', key, path);
assert(isfield(data, key), msg)
end
% ================== OPTIONAL keys ==================
% Bounds are linear ineq constraints are optional
% They should be cast to the double data type
% Or default to the correct empty shape
keys = {
"A_upper"; "B_upper"; "c_upper"; "d_upper"; "rhs_upper"; "s_upper";
"A_lower"; "B_lower"; "c_lower"; "d_lower"; "rhs_lower"; "s_lower";
"x_upper_bound"; "x_lower_bound"; ...
"y_upper_bound"; "y_lower_bound";...
};
default_values = {
zeros(0, data.n_x); zeros(0, data.n_y); zeros(0, 1); zeros(0, 1); zeros(0, 1); 0.0; ...
zeros(0, data.n_x); zeros(0, data.n_y); zeros(0, 1); zeros(0, 1); zeros(0, 1); 0.0; ...
zeros(0, 1); zeros(0, 1); ...
zeros(0, 1); zeros(0, 1); ...
};
for i = 1:length(keys)
key = keys{i};
default_value = default_values{i};
if ~isfield(data, key) || isempty(data.(key))
data.(key) = default_value;
else
data.(key) = double(data.(key));
end
end
% Final dimension check
quadratic_bilevel.validate_data_dimensions(data);
end
function validate_data_dimensions(data)
% VALIDATE_DATA_DIMENSIONS
% See the table of dimensions in the docstring at the top of this file.
n_x = data.n_x;
n_y = data.n_y;
n_G = numel(data.rhs_upper);
n_g = numel(data.rhs_lower);
mustBeSize = @(X, expected_size, key, allow_empty) assert( ...
isequal(size(X), expected_size) || (isempty(X) && allow_empty), ...
"Dimension of %s should be %s but got %s. See: '%s'.", ...
key, mat2str(expected_size), mat2str(size(X)), string(data.path) ...
);
% Upper-level
mustBeSize(data.A_upper, [n_G, n_x], 'A_upper', 0);
mustBeSize(data.B_upper, [n_G, n_y], 'B_upper', 0);
mustBeSize(data.c_upper, [n_x, 1], 'c_upper', 0);
mustBeSize(data.d_upper, [n_y, 1], 'd_upper', 0);
mustBeSize(data.P_upper, [n_x, n_x], 'P_upper', 0);
mustBeSize(data.Q_upper, [n_y, n_y], 'Q_upper', 0);
mustBeSize(data.R_upper, [n_x, n_y], 'R_upper', 0);
mustBeSize(data.s_upper, [1, 1], 's_upper', 0);
mustBeSize(data.rhs_upper, [n_G, 1], 'rhs_upper', 0);
% Lower-level
mustBeSize(data.A_lower, [n_g, n_x], 'A_lower', 0);
mustBeSize(data.B_lower, [n_g, n_y], 'B_lower', 0);
mustBeSize(data.c_lower, [n_x, 1], 'c_lower', 0);
mustBeSize(data.d_lower, [n_y, 1], 'd_lower', 0);
mustBeSize(data.P_lower, [n_x, n_x], 'P_lower', 0);
mustBeSize(data.Q_lower, [n_y, n_y], 'Q_lower', 0);
mustBeSize(data.R_lower, [n_x, n_y], 'R_lower', 0);
mustBeSize(data.s_lower, [1, 1], 's_lower', 0);
mustBeSize(data.rhs_lower, [n_g, 1], 'rhs_lower', 0);
% Bounds (allow empty or correct length)
mustBeSize(data.x_lower_bound, [n_x, 1], 'x_lower_bound', 1);
mustBeSize(data.x_upper_bound, [n_x, 1], 'x_upper_bound', 1);
mustBeSize(data.y_lower_bound, [n_y, 1], 'y_lower_bound', 1);
mustBeSize(data.y_upper_bound, [n_y, 1], 'y_upper_bound', 1);
end
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %
% -=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=- %
%% Dimension %%
% -=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=- %
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %
function n = dimension(key, data)
% Key is the function/variable name
% Value is it's dimension
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
endimport json
import os.path
from bolib3 import np
"""
Quadratic Bilevel Program (QBP)
===============================
The QBP has a quadratic objective function and linear constraints in both the upper and lower level.
The coefficients are stored in matrix form in the folder bolib3/data/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
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,) |
| P_upper | (n_x, n_x) |
| Q_upper | (n_y, n_y) |
| R_upper | (n_x, n_y) |
| s_upper | () |
| 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) |
| s_lower | () |
| rhs_lower | (n_g,) |
were n_x and n_y are the number of upper-level and lower-level decision variables respectively.
and n_G and n_g are the number of upper-level and lower-level inequality constraints respectively.
Example Python use case
=======================
from bolib3 import quadratic_bilevel
data = quadratic_bilevel.read_data("bolib3/data/quadratic_bilevel/aiyoshi_shimizu_1984_ex2.json")
x = np.array([25.0, 30.0])
y = np.array([5.0, 10.0])
print(quadratic_bilevel.g(x, y, data)) # [ 5. 0. 15. 20. 15. 10.]
"""
# Properties
name: str = "quadratic_bilevel"
category: str = "archetype"
subcategory: str = ""
author: str = "Samuel Ward"
# 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),
data['s_upper'].item()
))
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(data['A_upper']@x + 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),
data['s_lower'].item()
))
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(data['A_lower']@x + 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)
# %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
# -=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-
# Derivatives
# -=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-
# =============================================================
def derivative(func, wrt=None):
"""
This is a mapping of strings to the public functions.
Rather than calling df_dx(x, y) you may use derivative("f", wrt="x")(x, y)
Rather than calling f(x, y) you may use derivative("f", wrt=None)(x, y)
"""
mapping = {
# Upper-level
"F": {None: F, "x": dF_dx, "y": dF_dy, "xx": d2F_dxx, "yy": d2F_dyy, "xy": d2F_dxy},
"G": {None: G, "x": dG_dx, "y": dG_dy},
"H": {None: H, "x": dH_dx, "y": dH_dy},
# Lower-level
"f": {None: f, "x": df_dx, "y": df_dy, "xx": d2f_dxx, "yy": d2f_dyy, "xy": d2f_dxy},
"g": {None: g, "x": dg_dx, "y": dg_dy},
"h": {None: h, "x": dh_dx, "y": dh_dy},
}
return mapping[func][wrt]
def dF_dx(x, y, data):
"""First-order derivative of the upper-level objective function F(x,y) with respect to x"""
return data['P_upper']@x + data['R_upper']@y + data['c_upper']
def dF_dy(x, y, data):
"""First-order derivative of the upper-level objective function F(x,y) with respect to y"""
return data['Q_upper']@y + x@data['R_upper'] + data['d_upper']
def d2F_dxx(x, y, data):
"""Second-order derivative (Hessian) of the upper-level objective function F(x,y) w.r.t. x twice"""
return data['P_upper']
def d2F_dyy(x, y, data):
"""Second-order derivative (Hessian) of the upper-level objective function F(x,y) w.r.t. y twice"""
return data['Q_upper']
def d2F_dxy(x, y, data):
"""Second-order derivative (Hessian) of the upper-level objective function F(x,y) w.r.t. x and y"""
return data['R_upper']
def dG_dx(x, y, data):
"""Jacobian matrix of the upper-level inequality constraints G(x,y) with respect to x"""
jacobian_list = [np.empty((0, data['n_x']))]
if data['A_upper'].size:
jacobian_list.append(data['A_upper'])
if data['x_lower_bound'].size:
jacobian_list.append(np.identity(data['n_x']))
if data['x_upper_bound'].size:
jacobian_list.append(-1*np.identity(data['n_x']))
return np.concatenate(jacobian_list)
def dG_dy(x, y, data):
"""Jacobian matrix of the upper-level inequality constraints G(x,y) with respect to y"""
jacobian_list = [np.empty((0, data['n_y']))]
if data['B_upper'].size:
jacobian_list.append(data['B_upper'])
if data['x_lower_bound'].size:
jacobian_list.append(np.zeros((data['n_x'], data['n_y'])))
if data['x_upper_bound'].size:
jacobian_list.append(np.zeros((data['n_x'], data['n_y'])))
return np.concatenate(jacobian_list)
def dH_dx(x, y, data=None):
"""Jacobian matrix of the upper-level equality constraints H(x,y) with respect to x"""
return np.empty(0)
def dH_dy(x, y, data=None):
"""Jacobian matrix of the upper-level equality constraints H(x,y) with respect to y"""
return np.empty(0)
def df_dx(x, y, data):
"""First-order derivative of the lower-level objective function f(x,y) with respect to x"""
return data['P_lower']@x + data['R_lower']@y + data['c_lower']
def df_dy(x, y, data):
"""First-order derivative of the lower-level objective function f(x,y) with respect to y"""
return data['Q_lower']@y + x@data['R_lower'] + data['d_lower']
def d2f_dxx(x, y, data):
"""Second-order derivative (Hessian) of the lower-level objective function f(x,y) with respect x twice"""
return data['P_lower']
def d2f_dyy(x, y, data):
"""Second-order derivative (Hessian) of the lower-level objective function f(x,y) with respect to y twice"""
return data['Q_lower']
def d2f_dxy(x, y, data):
"""Second-order derivative (Hessian) of the lower-level objective function f(x,y) with respect to x and y"""
return data['R_lower']
def dg_dx(x, y, data):
"""Jacobian matrix of the lower-level inequality constraints g(x,y) with respect to x"""
jacobian_list = [np.empty((0, data['n_x']))]
if data['A_lower'].size:
jacobian_list.append(data['A_lower'])
if data['y_lower_bound'].size:
jacobian_list.append(np.zeros((data['n_y'], data['n_x'])))
if data['y_upper_bound'].size:
jacobian_list.append(np.zeros((data['n_y'], data['n_x'])))
return np.concatenate(jacobian_list)
def dg_dy(x, y, data):
"""Jacobian matrix of the lower-level inequality constraints g(x,y) with respect to y"""
jacobian_list = [np.empty((0, data['n_y']))]
if data['B_lower'].size:
jacobian_list.append(data['B_lower'])
if data['y_lower_bound'].size:
jacobian_list.append(np.identity(data['n_y']))
if data['y_upper_bound'].size:
jacobian_list.append(-1*np.identity(data['n_y']))
return np.concatenate(jacobian_list)
def dh_dx(x, y, data=None):
"""Jacobian matrix of the lower-level equality constraints h(x,y) with respect to x"""
return np.empty(0)
def dh_dy(x, y, data=None):
"""Jacobian matrix of the lower-level equality constraints h(x,y) with respect to y"""
return np.empty(0)
# %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
# -=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-
# Read Data
# -=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-
# =============================================================
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_ex4.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', 'qbp_16_24.json', 'qbp_27_27.json', 'qbp_2_3.json',
'qbp_32_48.json', 'qbp_3_3.json', 'qbp_4_6.json', 'qbp_8_12.json', 'qbp_9_9.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', 'toll_setting_p1.json', 'toll_setting_p2.json', 'toll_setting_p3.json',
'toll_setting_p4.json', 'toll_setting_p5.json', 'tuy_etal_2007.json', 'wan_wang_lv_2011.json',
'yezza_1996_ex31.json', 'yezza_1996_ex41.json'
]
paths: list = [
os.path.join("bolib3", "data", "quadratic_bilevel", d) for d in datasets
]
def read_data(path: str = datasets[0]):
"""
Must give a path to a JSON file with all the keys listed in required_data_fields.
For example, it should begin something like this:
{
"name": "author_1990",
"n_x": 2,
"n_y": 3,
"P_upper": [
[4.0, 5.0]
[6.0, 7.0]
],
"""
# Load the JSON file
with open(path, 'r') as file:
data = json.load(file)
# Store the path. This is useful diagnostics
data['path'] = path
# ================== REQUIRED keys ==================
# Dimensions and objective coefficients are nessasary
# They must be cast to the correct type
for key, expected_type in {
'n_x': int, 'n_y': int,
'P_upper': np.array, 'Q_upper': np.array, 'R_upper': np.array, 'c_upper': np.array, 'd_upper': np.array,
'P_lower': np.array, 'Q_lower': np.array, 'R_lower': np.array, 'c_lower': np.array, 'd_lower': np.array,
}.items():
assert key in data, f"Missing required key \"{key}\". See JSON file: {path}."
try:
data[key] = expected_type(data[key])
except TypeError:
raise (f"Value of \"{key}\": {data[key]} should be type \'{expected_type.__name__}\'. "
f"See in JSON file: {path}.")
# ================== OPTIONAL keys ==================
# Bounds and linear ineq constraints are optional
# They should be cast to numpy arrays
# Or default to the correct empty shape
for key, default_shape in {
"x_upper_bound": (0,), "x_lower_bound": (0,), "y_upper_bound": (0,), "y_lower_bound": (0,),
'A_upper': (0, data['n_x']), 'B_upper': (0, data['n_y']), "rhs_upper": (0,), 's_upper': (),
'A_lower': (0, data['n_x']), 'B_lower': (0, data['n_y']), "rhs_lower": (0,), 's_lower': ()
}.items():
if (key in data) and data[key]:
data[key] = np.array(data[key])
else:
data[key] = np.zeros(default_shape)
# Validate the dimensions of all arrays
_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, n_y, n_G, n_g = data['n_x'], data['n_y'], data['rhs_upper'].shape[0], data['rhs_lower'].shape[0]
identifier = "; ".join((data.get('name', ''), data.get('path', '')))
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),
's_upper': (),
'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),
's_lower': (),
'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}. See: '{identifier}'."
# %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
# -=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-
# Dimensions
# -=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-=x=-
# =============================================================
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