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.83e+05 -1.0 1.44e-02 - 1.00e+00 1.00e+00h 1
22 6.1333345e+00 0.00e+00 3.68e+05 -1.0 7.69e-03 - 1.00e+00 1.00e+00h 1
23 6.1333351e+00 2.22e-16 2.35e+06 -1.0 3.70e-03 - 1.00e+00 5.00e-01f 2
24 6.1333350e+00 2.22e-16 1.15e+07 -1.0 1.43e+00 - 3.06e-03 1.48e-04f 7
25 6.1333349e+00 2.22e-16 1.03e+07 -1.0 8.42e-02 1.8 1.03e-01 6.02e-03f 5
26 6.1333356e+00 0.00e+00 1.12e+06 -1.0 1.21e-02 2.2 8.79e-01 6.18e-01h 1
27 6.1333344e+00 0.00e+00 1.26e+06 -1.0 9.35e-03 - 8.18e-02 4.23e-02f 2
28 6.1333345e+00 0.00e+00 1.24e+06 -1.0 1.26e-02 - 6.93e-02 1.16e-03f 6
29 6.1333447e+00 0.00e+00 1.52e+06 -1.0 3.25e+00 5.3 8.33e-06 6.96e-05f 2
iter objective inf_pr inf_du lg(mu) ||d|| lg(rg) alpha_du alpha_pr ls
30 6.1333716e+00 0.00e+00 4.13e+07 -1.0 3.28e-04 6.6 1.00e+00 1.22e-01f 2
31 6.1333715e+00 1.11e-16 7.57e+02 -1.0 7.51e-05 - 1.00e+00 1.00e+00f 1
32 6.1333713e+00 0.00e+00 5.42e+04 -3.8 1.21e-06 - 9.97e-01 1.00e+00h 1
33 6.1333699e+00 0.00e+00 1.57e-02 -3.8 1.78e-05 - 1.00e+00 1.00e+00f 1
34 6.1333333e+00 0.00e+00 1.29e+04 -5.7 2.52e-04 - 5.00e-01 9.88e-01f 1
35 6.1333336e+00 8.72e-08 5.95e+04 -5.7 4.83e-01 - 1.69e-01 1.00e+00f 1
36 6.1333336e+00 6.65e-08 3.37e+04 -5.7 1.98e-07 6.2 9.46e-01 4.34e-01h 1
37 6.1333334e+00 1.11e-16 2.13e+04 -5.7 3.07e-01 - 2.71e-03 1.00e+00f 1
38 6.1333335e+00 2.79e-09 1.91e+03 -5.7 4.31e-08 5.7 1.00e+00 9.11e-01h 1
39 6.1333334e+00 0.00e+00 1.95e+03 -5.7 2.14e-01 - 2.68e-02 4.14e-01f 2
iter objective inf_pr inf_du lg(mu) ||d|| lg(rg) alpha_du alpha_pr ls
40 6.1333335e+00 0.00e+00 2.11e-02 -5.7 1.29e-07 5.2 1.00e+00 1.00e+00h 1
41 6.1333334e+00 2.59e-09 6.24e+01 -5.7 2.67e-01 - 6.50e-01 1.00e+00F 1
42 6.1333333e+00 1.11e-16 9.33e+00 -5.7 2.92e-02 - 1.00e+00 1.00e+00h 1
43 6.1333333e+00 4.44e-16 1.06e+02 -5.7 3.61e-01 - 6.50e-01 1.00e+00h 1
44 6.1333333e+00 0.00e+00 1.11e+03 -5.7 1.38e+00 - 5.74e-01 1.00e+00h 1
45 6.1333333e+00 4.44e-16 7.05e-04 -5.7 1.29e-08 4.7 1.00e+00 1.00e+00h 1
46 6.1333333e+00 1.78e-15 1.38e+03 -5.7 2.55e+00 - 7.82e-01 1.00e+00f 1
47 6.1333333e+00 0.00e+00 1.39e+03 -5.7 1.04e+01 - 7.93e-01 4.77e-01h 2
48 6.1333333e+00 0.00e+00 3.22e+02 -5.7 1.83e+00 - 1.00e+00 1.00e+00h 1
49 6.1333333e+00 0.00e+00 1.25e+01 -5.7 3.88e-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 4.19e-02 -5.7 1.78e-02 - 1.00e+00 1.00e+00h 1
51 6.1333333e+00 0.00e+00 7.01e-08 -5.7 1.15e-04 - 1.00e+00 1.00e+00h 1
52 6.1333333e+00 0.00e+00 2.37e+00 -8.6 3.39e-04 - 9.93e-01 1.00e+00h 1
In iteration 52, 1 Slack too small, adjusting variable bound
53 6.1333333e+00 0.00e+00 1.15e-01 -8.6 7.44e-01 - 9.51e-01 9.77e-01h 1
54 6.1333333e+00 0.00e+00 1.19e-01 -8.6 1.46e+00 - 1.00e+00 1.00e+00h 1
55 6.1333333e+00 0.00e+00 2.36e-02 -8.6 8.45e-01 - 1.00e+00 1.00e+00h 1
56 6.1333333e+00 0.00e+00 1.62e-04 -8.6 1.39e-01 - 1.00e+00 1.00e+00h 1
57 6.1333333e+00 0.00e+00 1.53e-09 -8.6 3.89e-04 - 1.00e+00 1.00e+00h 1
Number of Iterations....: 57
(scaled) (unscaled)
Objective...............: 6.1333332742376614e+00 6.1333332742376614e+00
Dual infeasibility......: 1.5310278091408371e-09 1.5310278091408371e-09
Constraint violation....: 0.0000000000000000e+00 0.0000000000000000e+00
Variable bound violation: 4.3702290096584022e-09 4.3702290096584022e-09
Complementarity.........: 2.5059035689687665e-09 2.5059035689687665e-09
Overall NLP error.......: 2.5059035689687665e-09 2.5059035689687665e-09
Number of objective function evaluations = 100
Number of objective gradient evaluations = 58
Number of equality constraint evaluations = 100
Number of inequality constraint evaluations = 100
Number of equality constraint Jacobian evaluations = 58
Number of inequality constraint Jacobian evaluations = 58
Number of Lagrangian Hessian evaluations = 57
Total seconds in IPOPT = 0.031
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.