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: Ipopt

First 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)

l4 : $ -7 y + 2 x \leq 0 $

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)
end

While 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)

objective_value(model)

objective_value(Lower(model))

value(x)

value(y)

value(u1)

value(l1)

dual(l1)

dual(l3)

1-element Vector{Float64}:
 4.370229009658402e-9

This page was generated using Literate.jl.