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)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 1.36e-13 4.55e+06 -1.0 3.44e-02 - 1.00e+00 3.38e-01f 2
19 1.1729935e-01 6.36e-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 1.11e-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 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 1.66e-13 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 1.11e-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.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 4.44e-16 1.14e+04 -5.7 1.01e-01 - 1.69e-02 1.00e+00h 1
42 -9.9995976e-01 2.22e-16 6.91e+00 -5.7 1.70e-05 2.5 5.92e-01 1.00e+00h 1
43 -9.9996269e-01 0.00e+00 5.18e+01 -5.7 2.94e-03 - 7.03e-01 1.00e+00h 1
44 -9.9996331e-01 2.22e-16 5.84e+01 -5.7 9.89e-04 - 6.62e-01 1.00e+00h 1
45 -9.9996444e-01 2.22e-16 5.69e+00 -5.7 5.69e-03 - 9.14e-01 1.00e+00H 1
46 -9.9996932e-01 2.22e-16 1.82e-01 -5.7 1.27e-03 - 1.00e+00 1.00e+00h 1
47 -9.9997063e-01 2.22e-16 5.56e-03 -5.7 5.39e-04 - 1.00e+00 1.00e+00h 1
48 -9.9997061e-01 2.22e-16 6.28e-05 -5.7 1.30e-05 - 1.00e+00 1.00e+00h 1
49 -9.9997061e-01 2.22e-16 3.16e-08 -5.7 3.37e-07 - 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 2.22e-16 4.38e+01 -8.6 2.53e-01 - 5.00e-01 1.44e-02h 1
52 -1.0000000e+00 3.35e-13 6.27e+01 -8.6 7.30e-03 - 1.81e-01 1.00e+00f 1
53 -1.0000000e+00 3.79e-13 7.94e+00 -8.6 9.20e-03 - 7.81e-01 1.00e+00h 1
54 -1.0000000e+00 2.22e-16 4.63e+00 -8.6 1.46e+00 - 4.14e-01 1.00e+00h 1
55 -1.0000000e+00 2.22e-16 7.34e-01 -8.6 2.45e-01 - 8.78e-01 1.00e+00h 1
56 -1.0000000e+00 1.78e-15 8.17e-01 -8.6 6.69e+00 - 4.13e-01 1.00e+00h 1
57 -1.0000000e+00 1.78e-15 7.56e-01 -8.6 3.57e+00 - 9.91e-01 1.00e+00h 1
58 -1.0000000e+00 1.11e-16 2.73e-06 -8.6 2.49e-08 2.0 1.00e+00 1.00e+00h 1
59 -1.0000000e+00 4.44e-16 1.02e+00 -8.6 1.21e+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 8.88e-16 1.30e+00 -8.6 4.69e+01 - 6.60e-02 9.64e-02h 2
61 -1.0000000e+00 5.96e-08 2.21e+00 -8.6 5.00e+01 - 3.18e-01 7.53e-01h 1
62 -1.0000000e+00 2.43e-07 2.14e+00 -8.6 1.17e+03 - 9.30e-03 3.19e-02f 2
63 -1.0000000e+00 1.50e-07 2.12e+00 -8.6 1.46e+03 - 9.52e-03 9.57e-03h 3
64 -1.0000001e+00 1.11e-16 7.39e-06 -8.6 2.02e-07 1.6 1.00e+00 1.00e+00h 1
65 -1.0000000e+00 3.55e-15 3.61e+00 -8.6 7.47e+01 - 4.48e-01 1.00e+00f 1
66 -1.0000000e+00 2.22e-16 3.22e-06 -8.6 2.64e-07 1.1 1.00e+00 1.00e+00h 1
67 -1.0000000e+00 7.11e-15 1.91e+00 -8.6 1.48e+02 - 8.66e-01 1.00e+00h 1
In iteration 67, 1 Slack too small, adjusting variable bound
68 -1.0000000e+00 1.37e-06 4.96e+00 -8.6 1.31e+03 - 1.22e-01 5.00e-01h 1
69 -1.0000000e+00 2.22e-16 2.77e-06 -8.6 6.82e-07 0.6 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 2.27e-13 1.71e+00 -8.6 9.37e+02 - 9.81e-01 1.00e+00h 1
In iteration 70, 1 Slack too small, adjusting variable bound
71 -1.0000001e+00 1.69e-04 6.73e+01 -8.6 2.51e+04 - 5.37e-02 8.93e-01h 1
72 -1.0000000e+00 2.22e-16 1.41e-05 -8.6 1.04e-05 0.1 1.00e+00 1.00e+00h 1
73 -1.0000000e+00 7.28e-12 1.27e+00 -8.6 1.89e+04 - 1.00e+00 1.00e+00h 1
74 -1.0000000e+00 2.91e-11 3.25e-01 -8.6 1.63e+05 - 1.00e+00 1.00e+00h 1
75 -1.0000000e+00 2.91e-11 1.20e-01 -8.6 4.49e+04 - 1.00e+00 1.00e+00h 1
76 -1.0000000e+00 2.22e-16 7.64e-05 -8.6 5.21e+02 - 1.00e+00 1.00e+00h 1
77 -1.0000000e+00 2.22e-16 4.19e-07 -8.6 9.67e+01 - 1.00e+00 1.00e+00h 1
78 -1.0000000e+00 2.22e-16 2.51e-14 -8.6 4.33e-02 - 1.00e+00 1.00e+00h 1
Number of Iterations....: 78
(scaled) (unscaled)
Objective...............: -1.0000000311605095e+00 -1.0000000311605095e+00
Dual infeasibility......: 2.5091040356528538e-14 2.5091040356528538e-14
Constraint violation....: 2.2204460492503131e-16 2.2204460492503131e-16
Variable bound violation: 0.0000000000000000e+00 0.0000000000000000e+00
Complementarity.........: 2.5059036178936522e-09 2.5059036178936522e-09
Overall NLP error.......: 2.5059036178936522e-09 2.5059036178936522e-09
Number of objective function evaluations = 109
Number of objective gradient evaluations = 79
Number of equality constraint evaluations = 109
Number of inequality constraint evaluations = 109
Number of equality constraint Jacobian evaluations = 79
Number of inequality constraint Jacobian evaluations = 79
Number of Lagrangian Hessian evaluations = 78
Total seconds in IPOPT = 0.093
EXIT: Optimal Solution Found.primal_status(model)FEASIBLE_POINT::ResultStatusCode = 1
termination_status(model)LOCALLY_SOLVED::TerminationStatusCode = 4
Results
objective_value(model)-1.0000000311605095
value.(x)7-element Vector{Float64}:
-2.9767438177527296e-9
-4.095847337666103e-9
-4.9635026964561474e-9
-2.9767438415143356e-9
-4.095847320507293e-9
-4.095847314053359e-9
-4.095847340508948e-9value.(ya)7-element Vector{Float64}:
1.0000000043870787
1.0000000057790928
1.0000000068664785
1.0000000043870785
1.0000000057790928
1.0000000057790928
1.0000000057790928value.(yb)7-element Vector{Float64}:
-4.387078578529712e-9
-5.7790928194903446e-9
-6.866478643743108e-9
-4.3870786084184025e-9
-5.7790927982076376e-9
-5.779092790202585e-9
-5.77909282301643e-9value(z)1.0000000038601298
This page was generated using Literate.jl.