Princeton Handbook of Test Problems: Test 9.3.4

This example is from the book Princeton Handbook of Test Problems in Local and Global Optimization Dempe, Chapter 9.3.4 -parg 223 url

Here, only the second level is described

Model of the problem First level

\[\min 2x_1+2x_2-3y_1-3y_2-60,\\ \notag s.t.\\ x_1 + x_2 + y_1 -2y_2 -40\leq 0,\\ 0 \leq x_i \leq 50, \forall i \in I,\\ -10 \leq y_j \leq 20, \forall j \in J,\\\]

Second level

\[\min (-x_1 + y_1 + 40)^2 + (-x_2 + y_2 + 20)^2,\\ \notag s.t.\\ - x_i + 2y_j <= -10,\forall (i,j) \in \{(i,j)|i\in I, j\in J, i=j\},\\ -10 \leq y_j \leq 20, \forall j \in J.\\\]

using BilevelJuMP
using Ipopt

model = BilevelModel(Ipopt.Optimizer; mode = BilevelJuMP.ProductMode(1e-9))
An Abstract JuMP Model
Feasibility problem with:
Variables: 0
Upper Constraints: 0
Lower Constraints: 0
Bilevel Model
Solution method: BilevelJuMP.ProductMode{Float64}(1.0e-9, false, 0, nothing)
Solver name: Ipopt

First we need to create all of the variables in the upper and lower problems:

Upper level variables

@variable(Upper(model), x[i = 1:2], start = 0)
2-element Vector{BilevelVariableRef}:
 x[1]
 x[2]

Lower level variables

@variable(Lower(model), y[i = 1:2], start = -10)
2-element Vector{BilevelVariableRef}:
 y[1]
 y[2]

Then we can add the objective and constraints of the upper problem:

Upper level objecive function

@objective(Upper(model), Min, 2x[1] + 2x[2] - 3y[1] - 3y[2] - 60)

\[ 2 x_{1} + 2 x_{2} - 3 y_{1} - 3 y_{2} - 60 \]

Upper level constraints

@constraint(Upper(model), x[1] + x[2] + y[1] - 2y[2] - 40 <= 0)
@constraint(Upper(model), [i = 1:2], x[i] >= 0)
@constraint(Upper(model), [i = 1:2], x[i] <= 50)
@constraint(Upper(model), [i = 1:2], y[i] >= -10)
@constraint(Upper(model), [i = 1:2], y[i] <= 20)
2-element Vector{ConstraintRef{BilevelModel, Int64, ScalarShape}}:
 y[1] ≤ 20
 y[2] ≤ 20

Followed by the objective and constraints of the lower problem:

Lower objective function

@objective(Lower(model), Min, (-x[1] + y[1] + 40)^2 + (-x[2] + y[2] + 20)^2)

\[ x_{1}^2 - 2 y_{1}\times x_{1} + y_{1}^2 + x_{2}^2 - 2 y_{2}\times x_{2} + y_{2}^2 - 80 x_{1} + 80 y_{1} - 40 x_{2} + 40 y_{2} + 2000 \]

Lower constraints

@constraint(Lower(model), [i = 1:2], -x[i] + 2y[i] <= -10)
@constraint(Lower(model), [i = 1:2], y[i] >= -10)
@constraint(Lower(model), [i = 1:2], y[i] <= 20)
2-element Vector{ConstraintRef{BilevelModel, Int64, ScalarShape}}:
 y[1] ≤ 20
 y[2] ≤ 20

Now we can solve the problem and verify the solution again that reported by the book

optimize!(model)
This is Ipopt version 3.14.4, running with linear solver MUMPS 5.4.1.

Number of nonzeros in equality constraint Jacobian...:       10
Number of nonzeros in inequality constraint Jacobian.:       42
Number of nonzeros in Lagrangian Hessian.............:        8

Total number of variables............................:       10
                     variables with only lower bounds:        2
                variables with lower and upper bounds:        0
                     variables with only upper bounds:        4
Total number of equality constraints.................:        2
Total number of inequality constraints...............:       21
        inequality constraints with only lower bounds:        6
   inequality constraints with lower and upper bounds:        0
        inequality constraints with only upper bounds:       15

iter    objective    inf_pr   inf_du lg(mu)  ||d||  lg(rg) alpha_du alpha_pr  ls
   0  0.0000000e+00 6.00e+01 9.57e-01  -1.0 0.00e+00    -  0.00e+00 0.00e+00   0
   1  4.4814823e-01 5.98e+01 1.28e+00  -1.0 5.21e+01    -  2.06e-03 4.18e-03h  1
   2  1.6046697e+00 5.89e+01 2.12e+00  -1.0 4.35e+01    -  1.53e-03 1.42e-02h  1
   3  1.6995414e+01 4.70e+01 1.06e+01  -1.0 3.84e+01    -  8.81e-03 2.02e-01h  1
   4  1.9250234e+01 4.52e+01 3.77e+01  -1.0 3.00e+01    -  1.34e-01 3.79e-02h  1
   5  3.5204890e+01 2.81e+01 6.90e+01  -1.0 2.11e+01    -  3.21e-02 3.78e-01h  1
   6  3.7687463e+01 2.21e+01 1.93e+02  -1.0 1.84e+01   0.0 1.54e-02 2.14e-01h  1
   7  3.8166798e+01 2.11e+01 8.95e+01  -1.0 1.36e+01   0.4 5.36e-01 4.66e-02h  1
   8  3.4396171e+01 1.82e+01 3.30e+02  -1.0 5.43e+01    -  4.41e-01 1.37e-01f  1
   9  3.3236150e+01 1.66e+01 2.79e+02  -1.0 2.52e+01    -  5.77e-02 8.71e-02f  1
iter    objective    inf_pr   inf_du lg(mu)  ||d||  lg(rg) alpha_du alpha_pr  ls
  10  3.0766710e+01 1.60e+01 4.15e+02  -1.0 4.61e+01    -  3.12e-01 3.79e-02f  1
  11  1.0078764e+01 1.11e+01 3.77e+02  -1.0 8.40e+01    -  5.03e-01 3.05e-01f  1
  12  2.4302311e-01 9.16e+00 4.41e+02  -1.0 6.72e+01    -  2.05e-02 1.75e-01f  1
  13  1.1671615e-01 4.12e+00 3.93e+02  -1.0 9.35e+00    -  1.00e+00 5.50e-01h  1
  14  1.7254023e-01 1.32e+00 5.89e+02  -1.0 4.03e+00    -  1.00e+00 6.79e-01h  1
  15  1.8014838e-01 7.75e-01 3.02e+03  -1.0 1.30e+00    -  1.00e+00 4.14e-01h  1
  16  1.9235506e-01 2.03e-01 2.82e+03  -1.0 7.56e-01    -  1.00e+00 7.38e-01h  1
  17  1.9390169e-01 1.15e-01 1.85e+04  -1.0 1.99e-01    -  1.00e+00 4.33e-01h  1
  18  1.9562312e-01 3.19e-02 1.96e+04  -1.0 1.12e-01    -  1.00e+00 7.22e-01h  1
  19  1.9604520e-01 1.79e-02 1.16e+05  -1.0 3.12e-02    -  1.00e+00 4.38e-01h  1
iter    objective    inf_pr   inf_du lg(mu)  ||d||  lg(rg) alpha_du alpha_pr  ls
  20  1.9619242e-01 4.98e-03 1.23e+05  -1.0 1.75e-02    -  1.00e+00 7.22e-01h  1
  21  1.9632743e-01 3.88e-03 9.52e+05  -1.0 4.75e-03    -  1.00e+00 2.21e-01f  2
  22  1.9565901e-01 1.07e-03 6.21e+05  -1.0 4.19e-03    -  1.00e+00 7.24e-01h  1
  23  1.9573024e-01 1.02e-03 4.02e+06  -1.0 8.16e-04    -  1.00e+00 4.36e-02f  5
  24  1.9569163e-01 1.11e-04 7.43e+05  -1.0 7.92e-04    -  1.00e+00 8.91e-01h  1
  25  1.9645947e-01 8.32e-05 5.40e+06  -1.0 2.01e-03    -  1.00e+00 2.51e-01f  2
  26  1.9874099e-01 0.00e+00 6.83e+02  -1.0 1.51e-03    -  1.00e+00 1.00e+00h  1
  27  6.8772523e-03 0.00e+00 8.22e+04  -2.5 9.71e-02    -  1.00e+00 1.00e+00f  1
  28  5.6568726e-03 1.42e-14 3.16e+00  -2.5 1.19e-03    -  1.00e+00 1.00e+00f  1
  29  3.0104856e-04 0.00e+00 6.46e+01  -3.8 2.68e-03    -  1.00e+00 1.00e+00f  1
iter    objective    inf_pr   inf_du lg(mu)  ||d||  lg(rg) alpha_du alpha_pr  ls
  30  3.0100656e-04 7.11e-15 7.46e-07  -3.8 2.57e-07    -  1.00e+00 1.00e+00h  1
  31  1.6349148e-07 1.42e-14 5.98e+00  -8.6 1.50e-04    -  1.00e+00 1.00e+00f  1
  32 -3.6266876e-08 7.11e-15 5.60e-03  -8.6 2.01e-06    -  1.00e+00 9.89e-01h  1
  33 -3.2290252e-08 7.11e-15 1.03e-12  -8.6 3.07e-08    -  1.00e+00 1.00e+00f  1

Number of Iterations....: 33

                                   (scaled)                 (unscaled)
Objective...............:  -3.2290252249822515e-08   -3.2290252249822515e-08
Dual infeasibility......:   1.0293987884324451e-12    1.0293987884324451e-12
Constraint violation....:   7.1054273576010019e-15    7.1054273576010019e-15
Variable bound violation:   4.8166666662694836e-09    4.8166666662694836e-09
Complementarity.........:   2.5157965771601277e-09    2.5157965771601277e-09
Overall NLP error.......:   2.5157965771601277e-09    2.5157965771601277e-09


Number of objective function evaluations             = 40
Number of objective gradient evaluations             = 34
Number of equality constraint evaluations            = 40
Number of inequality constraint evaluations          = 40
Number of equality constraint Jacobian evaluations   = 34
Number of inequality constraint Jacobian evaluations = 34
Number of Lagrangian Hessian evaluations             = 33
Total seconds in IPOPT                               = 0.020

EXIT: Optimal Solution Found.
primal_status(model)
FEASIBLE_POINT::ResultStatusCode = 1
termination_status(model)
LOCALLY_SOLVED::TerminationStatusCode = 4
objective_value(model)
-3.2290252249822515e-8
value.(x)
2-element Vector{Float64}:
 -8.74704822005564e-9
 -8.747048220161989e-9
value.(y)
2-element Vector{Float64}:
 -10.000000000634314
 -10.000000000264999

Like any other optimization problem, there is a chance in bilevel

optimization to find multiple solutions with the same optimal value; based on the inherent stochasticity of the algorithm and random seed, we are expecting two optimal solutions for this problem.


This page was generated using Literate.jl.