Foundations of Bilevel Programming: Chapter 3.2, Page 25
This example is from the book Foundations of Bilevel Programming by Stephan Dempe, Chapter 3.2, Page 25 url.
Model of the problem First level
\[\min 3x + y,\\ \notag s.t.\\ x \leq 5,\\ y \leq 8,\\ y \geq 0,\\\]
Second level
\[\min -x,\\ \notag s.t.\\ x + y <= 8,\\ 4x + y >= 8,\\ 2x + y <= 13,\\ 2x - y <= 0,\\\]
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 define all of the variables in the upper and lower problems:
@variable(Upper(model), y, start = 8 / 15)
@variable(Lower(model), x, start = 3.5 * 8 / 15)$ x $
Then we can add the objective and constraints of the upper problem: Upper level objective function
@objective(Upper(model), Min, 3x + y)$ 3 x + y $
Upper level constraints
@constraints(Upper(model), begin
u1, x <= 5
u2, y <= 8
u3, y >= 0
end)(u1 : x ≤ 5, u2 : y ≤ 8, u3 : y ≥ 0)
Followed by the objective and constraints of the lower problem: Lower level objective function
@objective(Lower(model), Min, -x)$ -x $
Lower level constraints
@constraint(Lower(model), l1, x + y <= 8)
@constraint(Lower(model), l2, 4x + y >= 8)
@constraint(Lower(model), l3, 2x + y <= 13)
@constraint(Lower(model), l4, 2x - 7y <= 0)\[ -7 y + 2 x \leq 0 \]
You can use the singular @constraint macro or the plural @constraints!
We can also set hints for the variables associated with the problems.
In this example, we know the duals on the lower constraints are in the set [-15, 15]:
for c in [l1, l2, l3, l4]
BilevelJuMP.set_dual_upper_bound_hint(c, 15)
BilevelJuMP.set_dual_lower_bound_hint(c, -15)
endWhile we think the primal variables are in [-10, 6] for x and [-1, 9] for y. These hints are optional. But supplying them (e.g., from domain knowledge) can be helpful for the solver.
BilevelJuMP.set_primal_lower_bound_hint(x, -10)
BilevelJuMP.set_primal_upper_bound_hint(x, 6)
BilevelJuMP.set_primal_lower_bound_hint(y, -1)
BilevelJuMP.set_primal_upper_bound_hint(y, 9)9
Now 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...: 4
Number of nonzeros in inequality constraint Jacobian.: 30
Number of nonzeros in Lagrangian Hessian.............: 8
Total number of variables............................: 6
variables with only lower bounds: 0
variables with lower and upper bounds: 6
variables with only upper bounds: 0
Total number of equality constraints.................: 1
Total number of inequality constraints...............: 11
inequality constraints with only lower bounds: 2
inequality constraints with lower and upper bounds: 0
inequality constraints with only upper bounds: 9
iter objective inf_pr inf_du lg(mu) ||d|| lg(rg) alpha_du alpha_pr ls
0 6.1333333e+00 9.90e-01 9.83e-01 -1.0 0.00e+00 - 0.00e+00 0.00e+00 0
1 6.1396885e+00 9.25e-01 9.34e-01 -1.0 2.24e-01 - 7.40e-02 6.55e-02h 1
2 6.1741160e+00 5.48e-01 8.00e+00 -1.0 5.64e-01 - 2.88e-01 4.08e-01f 1
3 6.1425229e+00 4.63e-01 6.88e+00 -1.0 1.11e+00 - 1.97e-01 1.55e-01h 1
4 6.1250014e+00 3.31e-01 1.58e+01 -1.0 4.82e-01 - 6.65e-01 2.85e-01h 1
5 6.1271581e+00 2.32e-01 4.43e+01 -1.0 1.38e+00 - 4.34e-01 2.99e-01h 1
6 6.1359708e+00 8.87e-03 7.84e+02 -1.0 1.46e+00 - 4.29e-01 9.62e-01h 1
7 6.1355776e+00 7.95e-03 1.73e+03 -1.0 2.63e-01 0.0 1.00e+00 1.04e-01h 1
8 6.1340660e+00 2.80e-03 1.39e+03 -1.0 3.22e-01 -0.5 1.00e+00 6.48e-01h 1
9 6.1336643e+00 1.18e-03 3.23e+03 -1.0 3.18e-01 - 1.00e+00 5.78e-01h 1
iter objective inf_pr inf_du lg(mu) ||d|| lg(rg) alpha_du alpha_pr ls
10 6.1335518e+00 4.87e-04 7.48e+03 -1.0 7.59e-01 - 1.00e+00 5.87e-01h 1
11 6.1334654e+00 2.01e-04 1.79e+04 -1.0 5.91e-01 - 1.00e+00 5.86e-01h 1
12 6.1334216e+00 8.31e-05 4.30e+04 -1.0 5.94e-01 - 1.00e+00 5.88e-01h 1
13 6.1333943e+00 3.41e-05 1.02e+05 -1.0 4.31e-01 - 1.00e+00 5.90e-01h 1
14 6.1333898e+00 2.90e-05 5.05e+05 -1.0 3.28e-01 - 1.00e+00 1.49e-01f 3
15 6.1333666e+00 6.15e-06 2.25e+05 -1.0 3.66e-01 - 1.00e+00 7.88e-01h 1
16 6.1333658e+00 5.26e-06 2.13e+06 -1.0 7.14e-02 - 1.00e+00 1.45e-01f 3
17 6.1333531e+00 1.14e-06 5.93e+05 -1.0 1.25e-01 - 1.00e+00 8.64e-01h 1
18 6.1333516e+00 9.44e-07 6.01e+06 -1.0 4.71e-02 - 1.00e+00 1.95e-01f 3
19 6.1333413e+00 1.32e-07 1.12e+05 -1.0 5.27e-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 6.1333412e+00 1.28e-07 2.35e+06 -1.0 2.43e-03 - 1.00e+00 1.38e-01f 2
21 6.1333372e+00 2.05e-08 4.84e+05 -1.0 1.44e-02 - 1.00e+00 1.00e+00h 1
22 6.1333345e+00 2.22e-16 3.71e+05 -1.0 7.67e-03 - 1.00e+00 1.00e+00h 1
23 6.1333351e+00 0.00e+00 2.36e+06 -1.0 3.68e-03 - 1.00e+00 5.00e-01f 2
24 6.1333351e+00 6.17e-11 1.82e+05 -1.0 5.20e-05 7.4 1.00e+00 1.22e-04f 14
25 6.1333346e+00 2.22e-16 9.24e+03 -1.0 7.68e-04 - 1.00e+00 1.00e+00h 1
26 6.1333344e+00 0.00e+00 7.07e+06 -1.7 1.48e-03 - 9.97e-01 5.00e-01f 2
27 6.1333343e+00 2.22e-16 1.37e+00 -1.7 1.33e-07 6.9 1.00e+00 1.00e+00f 1
28 6.1333343e+00 0.00e+00 8.18e-04 -5.7 4.28e-11 6.4 1.00e+00 1.00e+00h 1
29 6.1333336e+00 0.00e+00 1.37e-01 -5.7 5.74e-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 6.1333335e+00 1.11e-16 9.63e+00 -5.7 2.58e-01 - 6.85e-02 2.16e-02h 3
31 6.1333336e+00 2.22e-16 1.19e-01 -5.7 1.38e-07 5.9 1.00e+00 1.00e+00h 1
32 6.1333335e+00 0.00e+00 5.24e-01 -5.7 1.54e-02 - 1.00e+00 1.00e+00F 1
33 6.1333335e+00 0.00e+00 9.33e-03 -5.7 3.24e-08 5.5 1.00e+00 1.00e+00h 1
34 6.1333334e+00 1.11e-16 4.45e+01 -5.7 5.70e-02 - 7.62e-01 1.00e+00F 1
35 6.1333334e+00 0.00e+00 4.55e-03 -5.7 4.75e-08 5.0 1.00e+00 1.00e+00h 1
36 6.1333334e+00 2.81e-10 7.12e+01 -5.7 2.96e-01 - 7.57e-01 1.00e+00F 1
37 6.1333334e+00 0.00e+00 1.32e-03 -5.7 4.12e-08 4.5 1.00e+00 1.00e+00h 1
38 6.1333333e+00 0.00e+00 1.26e+02 -5.7 5.71e-01 - 5.56e-01 1.00e+00F 1
39 6.1333333e+00 0.00e+00 1.42e+04 -5.7 3.27e+00 - 2.46e-01 1.00e+00H 1
iter objective inf_pr inf_du lg(mu) ||d|| lg(rg) alpha_du alpha_pr ls
40 6.1333333e+00 0.00e+00 2.72e-04 -5.7 2.55e-08 4.0 1.00e+00 1.00e+00h 1
41 6.1333333e+00 0.00e+00 2.26e+03 -5.7 5.29e+00 - 8.71e-01 1.00e+00f 1
42 6.1333333e+00 0.00e+00 4.98e+02 -5.7 2.64e+00 - 1.00e+00 1.00e+00h 1
43 6.1333333e+00 0.00e+00 1.64e+01 -5.7 1.47e+00 - 1.00e+00 1.00e+00h 1
44 6.1333333e+00 0.00e+00 3.57e-02 -5.7 7.69e-02 - 1.00e+00 1.00e+00h 1
45 6.1333333e+00 0.00e+00 6.70e-06 -5.7 6.09e-04 - 1.00e+00 1.00e+00h 1
46 6.1333333e+00 0.00e+00 2.37e+00 -8.6 3.39e-04 - 9.93e-01 1.00e+00h 1
In iteration 46, 1 Slack too small, adjusting variable bound
47 6.1333333e+00 0.00e+00 1.15e-01 -8.6 7.44e-01 - 9.51e-01 9.77e-01h 1
48 6.1333333e+00 0.00e+00 1.19e-01 -8.6 1.46e+00 - 1.00e+00 1.00e+00h 1
49 6.1333333e+00 0.00e+00 2.36e-02 -8.6 8.45e-01 - 1.00e+00 1.00e+00h 1
iter objective inf_pr inf_du lg(mu) ||d|| lg(rg) alpha_du alpha_pr ls
50 6.1333333e+00 0.00e+00 1.62e-04 -8.6 1.39e-01 - 1.00e+00 1.00e+00h 1
51 6.1333333e+00 0.00e+00 1.53e-09 -8.6 3.89e-04 - 1.00e+00 1.00e+00h 1
Number of Iterations....: 51
(scaled) (unscaled)
Objective...............: 6.1333332742376614e+00 6.1333332742376614e+00
Dual infeasibility......: 1.5290959100556868e-09 1.5290959100556868e-09
Constraint violation....: 0.0000000000000000e+00 0.0000000000000000e+00
Variable bound violation: 4.3702290096584022e-09 4.3702290096584022e-09
Complementarity.........: 2.5059035689603818e-09 2.5059035689603818e-09
Overall NLP error.......: 2.5059035689603818e-09 2.5059035689603818e-09
Number of objective function evaluations = 89
Number of objective gradient evaluations = 52
Number of equality constraint evaluations = 89
Number of inequality constraint evaluations = 89
Number of equality constraint Jacobian evaluations = 52
Number of inequality constraint Jacobian evaluations = 52
Number of Lagrangian Hessian evaluations = 51
Total seconds in IPOPT = 0.024
EXIT: Optimal Solution Found.objective_value(model)6.133333274237661
objective_value(Lower(model))-1.866666648886298
value(x)1.866666648886298
value(y)0.5333333275787672
value(u1)1.866666648886298
value(l1)2.399999976465065
dual(l1)1-element Vector{Float64}:
4.017857147042123e-9dual(l3)1-element Vector{Float64}:
4.370229009658402e-9This page was generated using Literate.jl.