BASBLib - A Library of Bilevel Test Problems

A growing collection of bilevel problems

Linear-Quadratic type problem from [Aiyoshi & Shimizu, 1984]

Optimal solution

Objective values Solution points
F* = 0.000 x* = (0.0, 30.0)
f* = 100.000 y* = (-10.0, 10.0)
   
F* = 0.000 x* = (0.0, 0.0)
f* = 200.000 y* = (-10.0, -10.0)

The problem has a local solution at x = (25, 30), y = (5, 1O) for which the outer objective function is F = 5. The paper in which this problem is presented originally (Aiyoshi & Shimizu, 1984) locates this local optimum solution. (Shimizu et al., 1997) also report its local minimum as the solution of the problem.

Sources where this problem occur

Original source:

Other sources:

Description of the problem in the AMPL format

var x{1..2} >=   0, <= 50;    # Outer variable
var y{1..2} >= -10, <= 20;    # Inner variable
var l{1..6} >=   0, <= 100;   # KKT Multipliers

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

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

References