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: IpoptFirst 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] ≤ 20Followed 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] ≤ 20Now we can solve the problem and verify the solution again that reported by the book
optimize!(model)┌ Warning: primal_var_dual_quad_slack field is deprecated, use primal_var_in_quad_obj_to_dual_slack_var instead
└ @ Dualization ~/.julia/packages/Dualization/ihzlf/src/structures.jl:268
┌ Warning: primal_parameter field is deprecated, use primal_parameter_to_dual_parameter instead
└ @ Dualization ~/.julia/packages/Dualization/ihzlf/src/structures.jl:265
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 7.11e-15 6.83e+02 -1.0 1.51e-03 - 1.00e+00 1.00e+00h 1
27 6.8772523e-03 7.11e-15 8.22e+04 -2.5 9.71e-02 - 1.00e+00 1.00e+00f 1
28 5.6568726e-03 7.11e-15 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 0.00e+00 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.6264453e-08 2.58e-14 5.60e-03 -8.6 2.01e-06 - 1.00e+00 9.89e-01h 1
33 -3.2290220e-08 1.42e-14 1.03e-12 -8.6 3.06e-08 - 1.00e+00 1.00e+00f 1
Number of Iterations....: 33
(scaled) (unscaled)
Objective...............: -3.2290220275399406e-08 -3.2290220275399406e-08
Dual infeasibility......: 1.0289546992225951e-12 1.0289546992225951e-12
Constraint violation....: 1.4210854715202004e-14 1.4210854715202004e-14
Variable bound violation: 4.8166666662694828e-09 4.8166666662694828e-09
Complementarity.........: 2.5157965842376463e-09 2.5157965842376463e-09
Overall NLP error.......: 2.5157965842376463e-09 2.5157965842376463e-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.017
EXIT: Optimal Solution Found.primal_status(model)FEASIBLE_POINT::ResultStatusCode = 1
termination_status(model)LOCALLY_SOLVED::TerminationStatusCode = 4
objective_value(model)-3.2290220275399406e-8
value.(x)2-element Vector{Float64}:
-8.747048220055642e-9
-8.747048220161989e-9value.(y)2-element Vector{Float64}:
-10.000000000634323
-10.000000000265Like 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.