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)┌ Warning: primal_var_dual_quad_slack field is deprecated, use primal_var_in_quad_obj_to_dual_slack_var instead
└ @ Dualization ~/.julia/packages/Dualization/ihzlf/src/structures.jl:268
┌ Warning: primal_parameter field is deprecated, use primal_parameter_to_dual_parameter instead
└ @ Dualization ~/.julia/packages/Dualization/ihzlf/src/structures.jl:265
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 2.22e-16 3.69e+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.69e-03 - 1.00e+00 5.00e-01f 2
24 6.1333351e+00 6.09e-11 1.80e+05 -1.0 5.17e-05 7.4 1.00e+00 1.22e-04f 14
25 6.1333346e+00 1.11e-16 9.33e+03 -1.0 7.70e-04 - 1.00e+00 1.00e+00h 1
26 6.1333344e+00 1.11e-16 7.08e+06 -1.7 1.47e-03 - 9.98e-01 5.00e-01f 2
27 6.1333343e+00 0.00e+00 1.38e+00 -1.7 1.35e-07 6.9 1.00e+00 1.00e+00f 1
Cannot call restoration phase at point that is almost feasible (violation 0.000000e+00).
Abort in line search due to no other fall back.
Number of Iterations....: 27
(scaled) (unscaled)
Objective...............: 6.1333343314887925e+00 6.1333343314887925e+00
Dual infeasibility......: 1.3795753896608149e+00 1.3795753896608149e+00
Constraint violation....: 0.0000000000000000e+00 0.0000000000000000e+00
Variable bound violation: 4.3702287837121774e-09 4.3702287837121774e-09
Complementarity.........: 2.0955947486943651e-02 2.0955947486943651e-02
Overall NLP error.......: 2.0346336574443764e-04 1.3795753896608149e+00
Number of objective function evaluations = 77
Number of objective gradient evaluations = 29
Number of equality constraint evaluations = 77
Number of inequality constraint evaluations = 77
Number of equality constraint Jacobian evaluations = 29
Number of inequality constraint Jacobian evaluations = 29
Number of Lagrangian Hessian evaluations = 28
Total seconds in IPOPT = 0.017
EXIT: Error in step computation!objective_value(model)6.1333343314887925
objective_value(Lower(model))-1.8666669702000183
value(x)1.8666669702000183
value(y)0.5333334208887377
value(u1)1.8666669702000183
value(l1)2.400000391088756
dual(l1)1-element Vector{Float64}:
4.017856993477039e-9dual(l3)1-element Vector{Float64}:
4.370228783712177e-9This page was generated using Literate.jl.