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.6647533e-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 1.85e-13 4.55e+06 -1.0 3.44e-02 - 1.00e+00 3.38e-01f 2
19 1.1729935e-01 6.20e-14 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 1.11e-16 7.06e+04 -1.7 1.15e-01 - 1.00e+00 1.00e+00f 1
23 -6.9110326e-01 0.00e+00 4.17e+04 -1.7 2.12e-02 - 1.00e+00 1.00e+00f 1
24 -6.9625189e-01 2.22e-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 9.17e-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 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.9994749e-01 5.45e-08 1.17e+04 -5.7 1.01e-01 - 1.69e-02 5.00e-01h 2
42 -9.9995319e-01 5.98e-08 3.89e+03 -5.7 1.57e-05 2.5 1.00e+00 6.67e-01h 1
43 -9.9995574e-01 6.84e-09 4.29e+03 -5.7 6.90e-02 - 2.95e-03 3.81e-01f 2
44 -9.9995754e-01 3.27e-08 2.59e+03 -5.7 4.79e-05 2.0 1.00e+00 4.02e-01h 1
45 -9.9996263e-01 2.22e-16 2.23e+03 -5.7 2.46e-02 - 1.70e-02 1.00e+00f 1
46 -9.9996244e-01 2.22e-16 3.55e+01 -5.7 1.03e-04 1.6 8.16e-02 1.00e+00h 1
47 -9.9996297e-01 2.22e-16 3.12e-02 -5.7 1.67e-04 - 1.00e+00 1.00e+00h 1
48 -9.9997054e-01 1.11e-16 1.71e-01 -5.7 1.36e-03 - 1.00e+00 1.00e+00h 1
49 -9.9997070e-01 1.11e-16 5.72e-04 -5.7 1.05e-04 - 1.00e+00 1.00e+00h 1
iter objective inf_pr inf_du lg(mu) ||d|| lg(rg) alpha_du alpha_pr ls
50 -9.9997061e-01 2.22e-16 1.39e-05 -5.7 1.05e-05 - 1.00e+00 1.00e+00h 1
51 -1.0000000e+00 2.22e-16 1.67e+02 -8.6 1.83e-03 - 4.99e-01 9.98e-01f 1
52 -1.0000000e+00 1.75e-14 4.38e+01 -8.6 2.53e-01 - 5.00e-01 1.44e-02h 1
53 -1.0000000e+00 2.84e-13 6.27e+01 -8.6 7.30e-03 - 1.80e-01 1.00e+00f 1
54 -1.0000000e+00 1.55e-15 7.94e+00 -8.6 9.20e-03 - 7.81e-01 1.00e+00h 1
55 -1.0000000e+00 2.22e-16 4.63e+00 -8.6 1.46e+00 - 4.14e-01 1.00e+00h 1
56 -1.0000000e+00 2.22e-16 7.33e-01 -8.6 2.45e-01 - 8.78e-01 1.00e+00h 1
57 -1.0000000e+00 1.11e-16 8.13e-01 -8.6 6.69e+00 - 4.13e-01 1.00e+00h 1
58 -1.0000000e+00 1.78e-15 7.60e-01 -8.6 3.59e+00 - 9.91e-01 1.00e+00h 1
59 -1.0000000e+00 2.22e-16 3.04e-07 -8.6 2.49e-08 1.1 1.00e+00 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.02e+00 -8.6 1.21e+01 - 7.63e-01 1.00e+00h 1
61 -1.0000000e+00 0.00e+00 1.30e+00 -8.6 4.69e+01 - 6.70e-02 9.78e-02h 2
62 -1.0000000e+00 6.17e-08 2.23e+00 -8.6 5.00e+01 - 3.21e-01 7.59e-01h 1
63 -1.0000000e+00 1.11e-16 6.20e-08 -8.6 1.52e-08 0.6 1.00e+00 1.00e+00f 1
64 -1.0000000e+00 7.11e-15 2.30e+00 -8.6 6.98e+01 - 6.10e-01 1.00e+00h 1
In iteration 64, 1 Slack too small, adjusting variable bound
65 -1.0000000e+00 1.51e-07 2.96e+00 -8.6 2.33e+02 - 1.85e-01 3.72e-01h 1
66 -1.0000000e+00 2.22e-16 1.83e-07 -8.6 1.35e-07 0.1 1.00e+00 1.00e+00h 1
67 -1.0000000e+00 1.42e-14 1.61e+00 -8.6 2.29e+02 - 9.52e-01 1.00e+00h 1
68 -1.0000001e+00 2.34e-05 2.84e+01 -8.6 3.69e+03 - 8.23e-02 1.00e+00h 1
69 -1.0000000e+00 0.00e+00 4.94e-07 -8.6 1.09e-06 -0.3 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 4.55e-13 1.77e+00 -8.6 4.13e+03 - 9.92e-01 1.00e+00h 1
In iteration 70, 1 Slack too small, adjusting variable bound
71 -1.0000001e+00 2.69e-03 6.13e+01 -8.6 2.76e+05 - 3.45e-02 8.45e-01h 1
72 -1.0000000e+00 2.22e-16 1.05e-06 -8.6 6.97e-06 -0.8 1.00e+00 1.00e+00h 1
73 -1.0000000e+00 1.11e-16 4.27e-01 -8.6 4.99e+04 - 1.00e+00 1.00e+00h 1
74 -1.0000000e+00 2.91e-11 1.11e-03 -8.6 5.80e+04 - 1.00e+00 1.00e+00h 1
75 -1.0000000e+00 2.22e-16 5.28e-07 -8.6 1.59e+02 - 1.00e+00 1.00e+00h 1
76 -1.0000000e+00 2.22e-16 7.73e-14 -8.6 1.71e-02 - 1.00e+00 1.00e+00h 1
Number of Iterations....: 76
(scaled) (unscaled)
Objective...............: -1.0000000311605093e+00 -1.0000000311605093e+00
Dual infeasibility......: 7.7271522513910895e-14 7.7271522513910895e-14
Constraint violation....: 2.2204460492503131e-16 2.2204460492503131e-16
Variable bound violation: 0.0000000000000000e+00 0.0000000000000000e+00
Complementarity.........: 2.5059036298031712e-09 2.5059036298031712e-09
Overall NLP error.......: 2.5059036298031712e-09 2.5059036298031712e-09
Number of objective function evaluations = 105
Number of objective gradient evaluations = 77
Number of equality constraint evaluations = 105
Number of inequality constraint evaluations = 105
Number of equality constraint Jacobian evaluations = 77
Number of inequality constraint Jacobian evaluations = 77
Number of Lagrangian Hessian evaluations = 76
Total seconds in IPOPT = 0.077
EXIT: Optimal Solution Found.primal_status(model)FEASIBLE_POINT::ResultStatusCode = 1
termination_status(model)LOCALLY_SOLVED::TerminationStatusCode = 4
Results
objective_value(model)-1.0000000311605093
value.(x)7-element Vector{Float64}:
-2.9767438329184993e-9
-4.095847306191998e-9
-4.963502689373125e-9
-2.9767438229527195e-9
-4.095847330083533e-9
-4.095847311230549e-9
-4.095847317156543e-9value.(ya)7-element Vector{Float64}:
1.0000000043870787
1.0000000057790928
1.0000000068664785
1.0000000043870787
1.0000000057790928
1.0000000057790928
1.0000000057790928value.(yb)7-element Vector{Float64}:
-4.387078597606066e-9
-5.779092780452103e-9
-6.866478634715102e-9
-4.387078585070559e-9
-5.779092810085678e-9
-5.779092786701642e-9
-5.779092794051873e-9value(z)1.0000000038601298
This page was generated using Literate.jl.