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 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...: 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 0.00e+00 3.66e+05 -1.0 7.66e-03 - 1.00e+00 1.00e+00h 1
23 6.1333351e+00 0.00e+00 2.36e+06 -1.0 3.69e-03 - 1.00e+00 5.00e-01f 2
24 6.1333347e+00 2.22e-16 1.24e+03 -1.0 9.02e-05 - 1.00e+00 1.00e+00h 1
25 6.1333346e+00 1.11e-16 1.48e+04 -2.5 1.68e-04 - 1.00e+00 1.00e+00h 1
26 6.1333345e+00 1.11e-16 3.58e+01 -2.5 2.20e-05 1.8 1.00e+00 1.00e+00f 1
Cannot call restoration phase at point that is almost feasible (violation 1.110223e-16).
Abort in line search due to no other fall back.
Number of Iterations....: 26
(scaled) (unscaled)
Objective...............: 6.1333345125452912e+00 6.1333345125452912e+00
Dual infeasibility......: 3.5841188212015616e+01 3.5841188212015616e+01
Constraint violation....: 1.1102230246251565e-16 1.1102230246251565e-16
Variable bound violation: 4.3702289611215291e-09 4.3702289611215291e-09
Complementarity.........: 2.9671402126700249e-03 2.9671402126700249e-03
Overall NLP error.......: 3.7381382343713479e-02 3.5841188212015616e+01
Number of objective function evaluations = 51
Number of objective gradient evaluations = 28
Number of equality constraint evaluations = 51
Number of inequality constraint evaluations = 51
Number of equality constraint Jacobian evaluations = 28
Number of inequality constraint Jacobian evaluations = 28
Number of Lagrangian Hessian evaluations = 27
Total seconds in IPOPT = 0.047
EXIT: Error in step computation!objective_value(model)6.133334512545291
objective_value(Lower(model))-1.866667025303046
value(x)1.866667025303046
value(y)0.5333334366361542
value(u1)1.866667025303046
value(l1)2.4000004619392
dual(l1)1-element Vector{Float64}:
4.017857069584776e-9dual(l3)1-element Vector{Float64}:
4.370228961121529e-9This page was generated using Literate.jl.