Multiple second level problems

[joaquimg]

We could have a vector of those and just appends each KKT iteratively.

[joaquimg]

Add an example of how to model this with JuMP.@expression's

[skampezidou]

Here is one example with 2 lower-level programs:

using JuMP, BilevelJuMP, SCIP, HiGHS, Ipopt
a1 = 1
b1 = 4
c1 = 2
a2 = 1
b2 = 4
c2 = 2

model = BilevelModel(HiGHS.Optimizer, mode = BilevelJuMP.FortunyAmatMcCarlMode(primal_big_M = 100, dual_big_M = 100))

@variable(Lower(model), z1)
@variable(Lower(model), z2)
@variable(Upper(model), x[1:2])

@objective(Upper(model), Min, x[1]+3z1+3z2)
@Constraints(Upper(model), begin
x[1] + x[2] == 10
x[1] <= 6
x[1] >= 2
x[2] <= 8
x[2] >= 2
end)

@objective(Lower(model), Max, z1)
@Constraints(Lower(model), begin
z1 <= 20
z1 >= 0
x[1] + a1* z1 <= 8
x[1] + b1* z1 >= 8
x[1] + c1* z1 <= 13
end)

@objective(Lower(model), Max, z2)
@Constraints(Lower(model), begin
z2 <= 20
z2 >= 0
x[2] + a2* z2 <= 8
x[2] + b2* z2 >= 8
x[2] + c2* z2 <= 13
end)

optimize!(model)
println(objective_value(model))
println("Upper level variable values:")
println(value(x[1]))
println(value(x[2]))
println("Lower level variable values:")
println(value(z1))
println(value(z2))

However, the upper level variables are 2, 8 and the lower 1.5, 0 which is not correct (based on checking the results with another bilevel solver). See results here for comparison. Is my Julia implementation wrong? https://pao.readthedocs.io/en/latest/representations/pyomo.html#equation-eq-pao2:~:text=.value)-,2.0%208.0%205.5%200.0,-Trilevel%20Problems

If the order of the lower-level programs is changed (introduce the z2 lower program first), then the lower-level variable optimal values change, which makes me think that this is not a good implementation when you have multiple lower-level programs. What seems to be happening is that every new objective defined for another lower-level program replaces the previous objective defined for a previous lower-level program. This does not happen for the constraints which is nice. However, I have not been able to find a way to introduce multiple lower-level objectives so that all of them are considered in the KKT conditions extracted.

[joaquimg]

here is an example with multiple lower levels:
https://gist.github.com/joaquimg/0fdb18fccd8401952f41b35aaf3cf212

[joaquimg]

Is my Julia implementation wrong?

Yes, because you are creating a lower objective and then completely replacing it by a second one.

here is an example that works:

using BilevelJuMP, HiGHS
a1 = 1
b1 = 4
c1 = 2
a2 = 1
b2 = 4
c2 = 2

model = BilevelModel(HiGHS.Optimizer, mode = BilevelJuMP.FortunyAmatMcCarlMode(primal_big_M = 100, dual_big_M = 100))

@variable(Lower(model), z1)
@variable(Lower(model), z2)
@variable(Upper(model), x[1:2])

@objective(Upper(model), Min, x[1]+3z1+3z2)
@constraints(Upper(model), begin
x[1] + x[2] == 10
x[1] <= 6
x[1] >= 2
x[2] <= 8
x[2] >= 2
end)

# @objective(Lower(model), Max, z1) # this would create a complete objective function
obj1 = z1
@constraints(Lower(model), begin
z1 <= 20
z1 >= 0
x[1] + a1* z1 <= 8
x[1] + b1* z1 >= 8
x[1] + c1* z1 <= 13
end)

# @objective(Lower(model), Max, z2) # this would replace completely the objective function
obj2 = z2
@constraints(Lower(model), begin
z2 <= 20
z2 >= 0
x[2] + a2* z2 <= 8
x[2] + b2* z2 >= 8
x[2] + c2* z2 <= 13
end)

@objective(Lower(model), Max, obj1 + obj2)

optimize!(model)
println(objective_value(model))
println("Upper level variable values:")
println(value(x[1]))
println(value(x[2]))
println("Lower level variable values:")
println(value(z1))
println(value(z2))