Foundations of Bilevel Programming: Chapter 3.7, Page 59
This example is from the book Foundations of Bilevel Programming by Stephan Dempe, Chapter 3.7, Page 59. url
Model of the problem
First level
\[\min \sum_{i\in I} x_i - z,\\ \notag s.t.\\ y^a_i\geq 0, \forall i \in I,\\ y^a_i\leq 1, \forall i \in I,\\ y^b_i\geq 0, \forall i \in I,\\ y^b_i\leq 1, \forall i \in I,\\ y^a_i + y^b_i = 1, \forall i \in I,\\ z\geq 0,\\ z\leq 1,\\ y^a_1 + y^a_2 + y^a_3 \geq z,\\ -y^b_1 - y^b_4 + y^a_3 \geq z,\\ y^b_7 - y^b_6 + y^a_4 \geq z,\\ y^a_5 + y^a_6 + y^a_7 \geq z.\\\]
Second level
\[\min -\sum_{i\in I}x_i,\\ \notag s.t.\\ \sum x_i \geq 0,\\ x_i \leq y^a_i, \forall i\in I,\\ x_i \leq y^b_i, \forall i\in I,\\ I = \{1,...,7\}\]
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: IpoptGlobal variables
I = 7 # maximum literals
clauses = [[1, 2, 3], [-1, -4, 3], [7, -6, 4], [5, 6, 7]]4-element Vector{Vector{Int64}}:
[1, 2, 3]
[-1, -4, 3]
[7, -6, 4]
[5, 6, 7]First we need to create all of the variables in the upper and lower problems:
Upper level variables
@variable(Upper(model), ya[i = 1:I])
@variable(Upper(model), yb[i = 1:I])
@variable(Upper(model), z)
#Lower level variables
@variable(Lower(model), x[i = 1:I])7-element Vector{BilevelVariableRef}:
x[1]
x[2]
x[3]
x[4]
x[5]
x[6]
x[7]Then we can add the objective and constraints of the upper problem:
Upper level objective function
@objective(Upper(model), Min, sum(x[i] for i in 1:I) - z)$ x{1} + x{2} + x{3} + x{4} + x{5} + x{6} + x_{7} - z $
Upper level constraints
@constraint(Upper(model), ca, z <= 1)
@constraint(Upper(model), cb, z >= 0)
@constraint(Upper(model), c1[i = 1:I], ya[i] >= 0)
@constraint(Upper(model), c2[i = 1:I], ya[i] <= 1)
@constraint(Upper(model), c3[i = 1:I], yb[i] >= 0)
@constraint(Upper(model), c4[i = 1:I], yb[i] <= 1)
@constraint(Upper(model), c5[i = 1:I], ya[i] + yb[i] == 1)7-element Vector{ConstraintRef{BilevelModel, Int64, ScalarShape}}:
c5[1] : ya[1] + yb[1] = 1
c5[2] : ya[2] + yb[2] = 1
c5[3] : ya[3] + yb[3] = 1
c5[4] : ya[4] + yb[4] = 1
c5[5] : ya[5] + yb[5] = 1
c5[6] : ya[6] + yb[6] = 1
c5[7] : ya[7] + yb[7] = 1for c in clauses
@constraint(
Upper(model),
cc[k in eachindex(clauses)],
sum(i > 0 ? ya[i] : yb[-i] for i in clauses[k]) >= z
)4-element Vector{ConstraintRef{BilevelModel, Int64, ScalarShape}}:
cc[1] : ya[1] + ya[2] + ya[3] - z ≥ 0
cc[2] : ya[3] + yb[1] + yb[4] - z ≥ 0
cc[3] : ya[4] + ya[7] + yb[6] - z ≥ 0
cc[4] : ya[5] + ya[6] + ya[7] - z ≥ 0Followed by the objective and constraints of the lower problem:
Lower objective function
@objective(Lower(model), Min, -sum(x[i] for i in 1:I))$ -x{1} - x{2} - x{3} - x{4} - x{5} - x{6} - x_{7} $
Lower constraints
@constraint(Lower(model), b1[i = 1:I], x[i] >= 0)
@constraint(Lower(model), b2[i = 1:I], x[i] <= ya[i])
@constraint(Lower(model), b3[i = 1:I], x[i] <= yb[i])7-element Vector{ConstraintRef{BilevelModel, Int64, ScalarShape}}:
b3[1] : -yb[1] + x[1] ≤ 0
b3[2] : -yb[2] + x[2] ≤ 0
b3[3] : -yb[3] + x[3] ≤ 0
b3[4] : -yb[4] + x[4] ≤ 0
b3[5] : -yb[5] + x[5] ≤ 0
b3[6] : -yb[6] + x[6] ≤ 0
b3[7] : -yb[7] + x[7] ≤ 0Initial Starting conditions
JuMP.set_start_value.(x, 0)
JuMP.set_start_value.(ya, 1)
JuMP.set_start_value.(yb, 0)
JuMP.set_start_value(z, 1)
for i in 1:I
JuMP.set_dual_start_value.(b1, 0)
JuMP.set_dual_start_value.(b2, 0)
JuMP.set_dual_start_value.(b3, -1)
endNow we can solve the problem and verify the solution against that reported by Dempe.
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/lt5ES/src/structures.jl:251
┌ Warning: primal_parameter field is deprecated, use primal_parameter_to_dual_parameter instead
└ @ Dualization ~/.julia/packages/Dualization/lt5ES/src/structures.jl:248
This is Ipopt version 3.14.4, running with linear solver MUMPS 5.4.1.
Number of nonzeros in equality constraint Jacobian...: 35
Number of nonzeros in inequality constraint Jacobian.: 151
Number of nonzeros in Lagrangian Hessian.............: 35
Total number of variables............................: 43
variables with only lower bounds: 7
variables with lower and upper bounds: 0
variables with only upper bounds: 14
Total number of equality constraints.................: 14
Total number of inequality constraints...............: 76
inequality constraints with only lower bounds: 26
inequality constraints with lower and upper bounds: 0
inequality constraints with only upper bounds: 50
iter objective inf_pr inf_du lg(mu) ||d|| lg(rg) alpha_du alpha_pr ls
0 -1.0000000e+00 1.00e-02 1.00e+00 -1.0 0.00e+00 - 0.00e+00 0.00e+00 0
1 -5.2248049e-01 4.77e-03 3.99e+00 -1.0 2.38e-01 - 2.41e-01 6.17e-01f 1
2 -4.5537742e-01 3.78e-03 2.04e+01 -1.0 1.77e-01 - 9.29e-01 2.26e-01h 1
3 -3.1013603e-01 1.40e-03 9.72e+00 -1.0 2.14e-01 - 6.37e-01 5.95e-01h 1
4 -1.7909111e-01 6.25e-04 4.90e+01 -1.0 8.54e-02 - 1.00e+00 5.30e-01h 1
5 -5.2635494e-02 2.78e-04 1.17e+02 -1.0 1.39e-01 - 1.00e+00 5.91e-01h 1
6 4.8964938e-02 1.47e-04 6.07e+02 -1.0 1.00e-01 - 1.00e+00 4.74e-01h 1
7 4.3376478e-02 5.11e-05 7.49e+02 -1.0 1.68e-02 - 1.00e+00 6.42e-01h 1
8 1.3432903e-01 2.35e-05 2.28e+03 -1.0 8.17e-02 - 1.00e+00 5.62e-01h 1
9 1.0943512e-01 8.11e-06 3.70e+03 -1.0 2.46e-02 - 1.00e+00 6.45e-01h 1
iter objective inf_pr inf_du lg(mu) ||d|| lg(rg) alpha_du alpha_pr ls
10 1.9575626e-01 3.99e-06 1.16e+04 -1.0 7.13e-02 - 1.00e+00 5.69e-01h 1
11 1.1573775e-01 1.14e-06 2.02e+04 -1.0 6.21e-02 - 1.00e+00 6.60e-01h 1
12 1.3932121e-01 9.80e-07 1.25e+05 -1.0 7.48e-02 - 1.00e+00 1.47e-01f 3
13 3.0922874e-01 3.60e-07 6.62e+04 -1.0 1.06e-01 - 1.00e+00 7.60e-01h 1
14 2.9797374e-01 2.66e-07 5.55e+05 -1.0 3.64e-02 - 1.00e+00 1.48e-01f 3
15 1.6647532e-02 2.23e-08 1.70e+05 -1.0 1.54e-01 - 1.00e+00 8.49e-01h 1
16 1.9033881e-02 2.06e-08 3.39e+06 -1.0 6.15e-02 - 1.00e+00 1.75e-02f 6
17 1.0546868e-01 1.11e-08 6.84e+05 -1.0 4.30e-02 - 1.00e+00 8.78e-01h 1
18 1.2957235e-01 8.99e-13 4.55e+06 -1.0 3.44e-02 - 1.00e+00 3.38e-01f 2
19 1.1729935e-01 6.84e-13 6.80e+04 -1.0 1.79e-02 - 1.00e+00 1.00e+00h 1
iter objective inf_pr inf_du lg(mu) ||d|| lg(rg) alpha_du alpha_pr ls
20 2.0688419e-01 2.22e-16 3.19e+04 -1.0 4.11e-02 - 1.00e+00 1.00e+00f 1
21 -5.0650203e-01 2.22e-16 3.04e+06 -1.7 2.52e-01 - 7.50e-01 1.00e+00f 1
22 -7.1215007e-01 2.22e-16 7.06e+04 -1.7 1.15e-01 - 1.00e+00 1.00e+00f 1
23 -6.9110326e-01 2.22e-16 4.17e+04 -1.7 2.12e-02 - 1.00e+00 1.00e+00f 1
24 -6.9625189e-01 1.11e-16 2.86e+03 -1.7 4.13e-03 - 1.00e+00 1.00e+00f 1
25 -6.9564015e-01 2.22e-16 1.74e+01 -1.7 7.17e-04 - 1.00e+00 1.00e+00h 1
26 -9.7277264e-01 3.26e-14 1.52e+06 -3.8 8.89e-02 - 5.22e-01 9.68e-01f 1
27 -9.8930021e-01 2.22e-16 1.98e+06 -3.8 7.30e-03 - 2.50e-01 1.00e+00f 1
28 -9.9199990e-01 1.11e-16 2.08e+06 -3.8 2.47e-03 - 3.28e-01 1.00e+00f 1
29 -9.9200876e-01 2.22e-16 1.24e+05 -3.8 4.91e-05 4.0 8.47e-01 1.00e+00f 1
iter objective inf_pr inf_du lg(mu) ||d|| lg(rg) alpha_du alpha_pr ls
30 -9.9212721e-01 2.22e-16 3.24e-01 -3.8 3.94e-05 3.5 1.00e+00 1.00e+00f 1
31 -9.9243733e-01 2.22e-16 9.31e-01 -3.8 1.16e-04 3.0 1.00e+00 1.00e+00f 1
32 -9.9528003e-01 2.22e-16 1.70e+02 -3.8 1.02e-02 - 2.88e-01 1.44e-01f 2
33 -9.9624613e-01 2.22e-16 1.65e+05 -3.8 8.40e-03 - 1.00e+00 7.62e-02f 2
34 -9.9731688e-01 2.22e-16 2.15e+04 -3.8 6.72e-04 - 9.00e-01 1.00e+00f 1
35 -9.9755343e-01 1.11e-16 1.78e+00 -3.8 1.80e-04 - 1.00e+00 1.00e+00f 1
36 -9.9756559e-01 2.22e-16 7.69e-02 -3.8 2.70e-05 - 1.00e+00 1.00e+00f 1
37 -9.9984090e-01 2.22e-16 1.21e+04 -5.7 7.73e-04 - 4.89e-01 9.34e-01f 1
38 -9.9993263e-01 3.60e-07 8.98e+02 -5.7 1.04e-01 - 9.26e-01 1.00e+00f 1
39 -9.9996237e-01 8.52e-08 2.95e+03 -5.7 4.65e-02 - 4.99e-01 1.00e+00h 1
iter objective inf_pr inf_du lg(mu) ||d|| lg(rg) alpha_du alpha_pr ls
40 -9.9996194e-01 2.22e-16 4.45e+04 -5.7 2.58e-05 2.6 3.59e-02 1.00e+00h 1
41 -9.9996259e-01 1.93e-14 3.10e+04 -5.7 5.22e-05 2.1 9.83e-01 3.08e-01h 1
42 -9.9996447e-01 2.22e-16 1.73e-02 -5.7 6.77e-05 1.6 1.00e+00 1.00e+00f 1
43r-9.9996447e-01 2.22e-16 6.15e+02 -5.7 0.00e+00 - 0.00e+00 4.12e-07R 14
44r-9.9993044e-01 4.16e-11 8.66e+00 -5.7 4.15e-03 - 9.83e-01 1.00e+00f 1
45 -9.9993322e-01 4.55e-11 4.73e+02 -5.7 3.61e-02 - 2.53e-01 1.47e-03h 2
46 -9.9995627e-01 3.73e-11 3.47e+02 -5.7 3.55e-02 - 1.00e+00 1.81e-01h 2
47 -9.9996938e-01 1.11e-16 7.16e+00 -5.7 3.20e-02 - 1.00e+00 1.00e+00h 1
48 -9.9997302e-01 4.85e-08 1.88e+02 -5.7 1.21e-02 - 4.80e-01 1.00e+00h 1
49 -9.9997314e-01 1.45e-08 1.27e+02 -5.7 7.13e-03 - 1.00e+00 4.80e-01h 2
iter objective inf_pr inf_du lg(mu) ||d|| lg(rg) alpha_du alpha_pr ls
50 -9.9997282e-01 6.96e-09 1.02e+02 -5.7 8.19e-03 - 8.00e-01 3.88e-01h 2
51 -9.9997200e-01 4.71e-09 7.57e+01 -5.7 4.91e-03 - 4.79e-01 3.24e-01h 2
52 -9.9996975e-01 2.22e-16 1.13e-01 -5.7 7.26e-04 - 1.00e+00 1.00e+00h 1
53 -9.9997059e-01 2.22e-16 1.13e-02 -5.7 4.88e-04 - 1.00e+00 1.00e+00h 1
54 -9.9997062e-01 2.22e-16 9.56e-04 -5.7 1.49e-04 - 1.00e+00 1.00e+00h 1
55 -9.9997061e-01 1.11e-16 3.71e-07 -5.7 1.15e-06 - 1.00e+00 1.00e+00h 1
56 -1.0000000e+00 2.22e-16 1.67e+02 -8.6 1.83e-03 - 4.99e-01 9.98e-01f 1
57 -1.0000000e+00 1.33e-14 4.38e+01 -8.6 2.53e-01 - 5.00e-01 1.44e-02h 1
58 -1.0000000e+00 2.89e-11 6.23e+01 -8.6 7.30e-03 - 1.86e-01 1.00e+00f 1
59 -1.0000000e+00 2.22e-16 7.81e+00 -8.6 9.17e-03 - 7.83e-01 1.00e+00h 1
iter objective inf_pr inf_du lg(mu) ||d|| lg(rg) alpha_du alpha_pr ls
60 -1.0000000e+00 2.22e-16 4.59e+00 -8.6 1.49e+00 - 4.09e-01 1.00e+00h 1
61 -1.0000000e+00 2.22e-16 7.20e-01 -8.6 2.48e-01 - 8.79e-01 1.00e+00h 1
62 -1.0000000e+00 2.22e-16 3.93e-01 -8.6 7.28e+00 - 3.84e-01 1.00e+00h 1
63 -1.0000000e+00 2.22e-16 3.27e-01 -8.6 2.85e+00 - 9.93e-01 1.00e+00h 1
64 -1.0000000e+00 1.11e-16 3.58e-07 -8.6 2.61e-08 1.1 1.00e+00 1.00e+00h 1
65 -1.0000000e+00 4.44e-16 1.09e+00 -8.6 1.23e+01 - 7.67e-01 1.00e+00h 1
66 -1.0000000e+00 3.55e-15 1.25e+00 -8.6 5.15e+01 - 5.68e-02 8.17e-02h 2
67 -1.0000000e+00 3.98e-08 1.96e+00 -8.6 5.46e+01 - 2.90e-01 6.80e-01h 1
In iteration 67, 1 Slack too small, adjusting variable bound
68 -1.0000000e+00 1.96e-07 4.69e+00 -8.6 9.30e+01 - 1.82e-01 4.94e-01f 1
69 -1.0000000e+00 2.22e-16 1.07e-06 -8.6 2.33e-07 0.7 1.00e+00 1.00e+00h 1
iter objective inf_pr inf_du lg(mu) ||d|| lg(rg) alpha_du alpha_pr ls
70 -1.0000000e+00 1.42e-14 2.76e+00 -8.6 1.34e+02 - 6.99e-01 1.00e+00f 1
71 -1.0000000e+00 2.22e-16 1.92e-07 -8.6 1.26e-07 0.2 1.00e+00 1.00e+00h 1
72 -1.0000000e+00 1.42e-14 1.59e+00 -8.6 2.48e+02 - 9.92e-01 1.00e+00h 1
73 -1.0000000e+00 1.33e-04 4.25e+01 -8.6 2.91e+04 - 2.72e-02 1.00e+00h 1
74 -1.0000000e+00 1.11e-16 9.24e-07 -8.6 1.82e-06 -0.3 1.00e+00 1.00e+00h 1
75 -1.0000000e+00 4.55e-13 1.76e+00 -8.6 2.52e+04 - 1.00e+00 1.00e+00f 1
76 -1.0000000e+00 5.82e-11 1.41e+02 -8.6 3.12e+05 - 1.08e-02 1.00e+00h 1
77 -1.0000000e+00 1.11e-16 3.35e-08 -8.6 1.98e-07 -0.8 1.00e+00 1.00e+00h 1
78 -1.0000000e+00 2.91e-11 5.74e-01 -8.6 1.78e+05 - 1.00e+00 1.00e+00h 1
79 -1.0000000e+00 2.22e-16 1.38e-05 -8.6 6.46e+04 - 1.00e+00 1.00e+00h 1
iter objective inf_pr inf_du lg(mu) ||d|| lg(rg) alpha_du alpha_pr ls
80 -1.0000000e+00 1.11e-16 4.67e-10 -8.6 3.99e+00 - 1.00e+00 1.00e+00h 1
Number of Iterations....: 80
(scaled) (unscaled)
Objective...............: -1.0000000311598189e+00 -1.0000000311598189e+00
Dual infeasibility......: 4.6700576739056032e-10 4.6700576739056032e-10
Constraint violation....: 1.1102230246251565e-16 1.1102230246251565e-16
Variable bound violation: 0.0000000000000000e+00 0.0000000000000000e+00
Complementarity.........: 2.5059036074312985e-09 2.5059036074312985e-09
Overall NLP error.......: 2.5059036074312985e-09 2.5059036074312985e-09
Number of objective function evaluations = 124
Number of objective gradient evaluations = 81
Number of equality constraint evaluations = 124
Number of inequality constraint evaluations = 124
Number of equality constraint Jacobian evaluations = 82
Number of inequality constraint Jacobian evaluations = 82
Number of Lagrangian Hessian evaluations = 80
Total seconds in IPOPT = 0.071
EXIT: Optimal Solution Found.primal_status(model)FEASIBLE_POINT::ResultStatusCode = 1
termination_status(model)LOCALLY_SOLVED::TerminationStatusCode = 4
Results
objective_value(model)-1.000000031159819
value.(x)7-element Vector{Float64}:
-2.9768637670153235e-9
-4.095847316563606e-9
-4.963427439516613e-9
-2.97686378020177e-9
-4.095847336377488e-9
-4.09584733644634e-9
-4.095847342815327e-9value.(ya)7-element Vector{Float64}:
1.0000000043872295
1.0000000057790928
1.0000000068663828
1.0000000043872295
1.0000000057790928
1.0000000057790928
1.0000000057790928value.(yb)7-element Vector{Float64}:
-4.387229458491102e-9
-5.779092793316138e-9
-6.866382721681826e-9
-4.387229475068213e-9
-5.779092817892027e-9
-5.779092817977427e-9
-5.779092825877118e-9value(z)1.0000000038592747
This page was generated using Literate.jl.