BASBLib - A Library of Bilevel Test Problems

A growing collection of bilevel problems

Linear-Linear problem from [Bard & Falk, 1982]:


Optimal solution

Objective values Solution point
F* = -3.250 x* = (2.000, 0.000)
f* = -4.000 y* = (1.500, 0.000)

In the original paper (Bard & Falk, 1982) a non-optimal solution is located at x = (1, 0), y = (0.5, 1) with an outer objective function value of F = -1.75.

Original source:

Other sources:

Description of the problem in the AMPL format

var x{1..2} >= 0, <= 10;   # Outer variable
var y{1..2} >= 0, <= 10;   # Inner variable
var l{1..7} >= 0, <= 10;   # KKT Multipliers

minimize outer_obj: -2*x[1] + x[2] + 0.5*y[1];  # Outer objective

subject to
# Inner objective:
    inner_obj: x[1] + x[2] - 4*y[1] + y[2] = 0;
# Inner constraints
    inner_con1: -2*x[1] + y[1] - y[2] + 2.5 <= 0;
    inner_con2: x[1] - 3*x[2] + y[2] - 2 <= 0;
    inner_con3: x[1] + x[2] - 2 <= 0;
# KKT conditions:
    stationarity_1:   -4 + l[1] - l[3] + l[4] = 0;
    stationarity_2:    1 - l[1] + l[2] - l[5] + l[6] = 0;
    complementarity_1: l[1]*(-2*x[1] + y[1]  - y[2] + 2.5) = 0;
    complementarity_2: l[2]*(x[1] - 3*x[2] + y[2] - 2) = 0;
    complementarity_3: l[3]*(x[1] + x[2] - 2) = 0;
    complementarity_4: l[4]*y[1] = 0;
    complementarity_5: l[5]*(y[1] - 10) = 0;
    complementarity_6: l[6]*y[2] = 0;
    complementarity_7: l[7]*(y[2] - 10) = 0;

References