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 objecive 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 again 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/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...: 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 3.02e-13 4.55e+06 -1.0 3.44e-02 - 1.00e+00 3.38e-01f 2
19 1.1729935e-01 1.10e-12 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 1.11e-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 8.86e-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 2.22e-16 2.08e+06 -3.8 2.47e-03 - 3.28e-01 1.00e+00f 1
29 -9.9200876e-01 1.11e-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 3.33e-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 2.22e-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.9989976e-01 3.62e-07 1.85e+04 -5.7 1.03e-01 - 4.15e-01 1.00e+00f 1
39 -9.9990102e-01 3.60e-07 1.79e+04 -5.7 1.67e-05 3.5 9.65e-01 3.71e-02h 1
iter objective inf_pr inf_du lg(mu) ||d|| lg(rg) alpha_du alpha_pr ls
40 -9.9994358e-01 2.38e-07 1.21e+04 -5.7 8.69e-05 3.0 1.00e+00 3.28e-01f 2
41 -9.9995140e-01 7.83e-10 1.14e+04 -5.7 1.01e-01 - 1.69e-02 1.00e+00h 1
42 -9.9995976e-01 2.22e-16 7.06e+00 -5.7 1.70e-05 2.5 5.87e-01 1.00e+00h 1
43 -9.9996269e-01 3.81e-14 5.17e+01 -5.7 2.93e-03 - 7.03e-01 1.00e+00h 1
44 -9.9996331e-01 2.22e-16 5.80e+01 -5.7 8.43e-04 - 6.63e-01 1.00e+00h 1
45 -9.9996439e-01 2.22e-16 7.98e+00 -5.7 6.08e-03 - 8.88e-01 1.00e+00H 1
46 -9.9996904e-01 1.11e-16 2.36e-01 -5.7 1.55e-03 - 1.00e+00 1.00e+00h 1
47 -9.9997065e-01 1.11e-16 3.48e-03 -5.7 6.18e-04 - 1.00e+00 1.00e+00h 1
48 -9.9997061e-01 1.11e-16 2.52e-04 -5.7 3.91e-05 - 1.00e+00 1.00e+00h 1
49 -9.9997061e-01 2.22e-16 8.18e-09 -5.7 5.98e-08 - 1.00e+00 1.00e+00h 1
iter objective inf_pr inf_du lg(mu) ||d|| lg(rg) alpha_du alpha_pr ls
50 -1.0000000e+00 2.22e-16 1.67e+02 -8.6 1.83e-03 - 4.99e-01 9.98e-01f 1
51 -1.0000000e+00 3.71e-14 4.38e+01 -8.6 2.53e-01 - 5.00e-01 1.44e-02h 1
52 -1.0000000e+00 1.33e-11 6.27e+01 -8.6 7.30e-03 - 1.81e-01 1.00e+00f 1
53 -1.0000000e+00 4.44e-16 7.89e+00 -8.6 9.18e-03 - 7.82e-01 1.00e+00h 1
54 -1.0000000e+00 4.44e-16 4.61e+00 -8.6 1.48e+00 - 4.12e-01 1.00e+00h 1
55 -1.0000000e+00 2.22e-16 7.49e-01 -8.6 2.50e-01 - 8.77e-01 1.00e+00h 1
56 -1.0000000e+00 2.22e-16 9.07e-01 -8.6 6.65e+00 - 4.19e-01 1.00e+00h 1
57 -1.0000000e+00 1.78e-15 8.20e-01 -8.6 3.63e+00 - 9.92e-01 1.00e+00h 1
58 -1.0000000e+00 2.22e-16 2.88e-06 -8.6 2.62e-08 2.0 1.00e+00 1.00e+00h 1
59 -1.0000000e+00 4.44e-16 9.97e-01 -8.6 1.19e+01 - 7.64e-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 3.55e-15 1.28e+00 -8.6 4.48e+01 - 6.36e-02 9.25e-02h 2
61 -1.0000000e+00 5.50e-08 2.16e+00 -8.6 4.77e+01 - 3.10e-01 7.38e-01h 1
In iteration 61, 1 Slack too small, adjusting variable bound
62 -1.0000000e+00 2.10e-07 2.69e+00 -8.6 1.64e+02 - 6.78e-02 2.13e-01f 1
63 -1.0000000e+00 2.22e-16 8.36e-02 -8.6 2.00e-07 1.6 9.02e-01 1.00e+00h 1
64 -1.0000000e+00 2.84e-14 4.51e+00 -8.6 9.64e+01 - 5.48e-01 1.00e+00f 1
65 -1.0000000e+00 2.22e-16 1.41e-06 -8.6 1.15e-07 1.1 1.00e+00 1.00e+00h 1
66 -1.0000000e+00 2.22e-16 1.72e+00 -8.6 1.83e+02 - 9.56e-01 1.00e+00h 1
67 -1.0000000e+00 2.14e-05 1.59e+01 -8.6 4.91e+03 - 1.25e-01 1.00e+00h 1
68 -1.0000000e+00 1.11e-16 6.75e-06 -8.6 1.66e-06 0.6 1.00e+00 1.00e+00h 1
69 -1.0000000e+00 1.82e-12 1.74e+00 -8.6 5.19e+03 - 9.94e-01 1.00e+00h 1
iter objective inf_pr inf_du lg(mu) ||d|| lg(rg) alpha_du alpha_pr ls
70 -1.0000000e+00 5.89e-04 7.23e+01 -8.6 1.66e+05 - 3.48e-02 1.00e+00h 1
71 -1.0000000e+00 2.22e-16 1.14e-06 -8.6 8.44e-07 0.1 1.00e+00 1.00e+00h 1
72 -1.0000000e+00 2.91e-11 1.78e-01 -8.6 4.35e+04 - 1.00e+00 1.00e+00h 1
73 -1.0000000e+00 2.91e-11 2.64e-04 -8.6 2.10e+04 - 1.00e+00 1.00e+00h 1
74 -1.0000000e+00 1.11e-16 2.13e-07 -8.6 7.87e+01 - 1.00e+00 1.00e+00h 1
75 -1.0000000e+00 1.11e-16 6.86e-14 -8.6 3.41e-02 - 1.00e+00 1.00e+00h 1
Number of Iterations....: 75
(scaled) (unscaled)
Objective...............: -1.0000000311598189e+00 -1.0000000311598189e+00
Dual infeasibility......: 6.8556271770603416e-14 6.8556271770603416e-14
Constraint violation....: 1.1102230246251565e-16 1.1102230246251565e-16
Variable bound violation: 0.0000000000000000e+00 0.0000000000000000e+00
Complementarity.........: 2.5059036088496266e-09 2.5059036088496266e-09
Overall NLP error.......: 2.5059036088496266e-09 2.5059036088496266e-09
Number of objective function evaluations = 100
Number of objective gradient evaluations = 76
Number of equality constraint evaluations = 100
Number of inequality constraint evaluations = 100
Number of equality constraint Jacobian evaluations = 76
Number of inequality constraint Jacobian evaluations = 76
Number of Lagrangian Hessian evaluations = 75
Total seconds in IPOPT = 0.078
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.9768637656044346e-9
-4.09584733776515e-9
-4.963427441852041e-9
-2.976863769925588e-9
-4.095847338753477e-9
-4.095847332243052e-9
-4.095847322046967e-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.38722945539115e-9
-5.7790928196131974e-9
-6.866382724659958e-9
-4.387229460826525e-9
-5.779092820839055e-9
-5.779092812763934e-9
-5.7790928001173536e-9value(z)1.0000000038592747
This page was generated using Literate.jl.