Multiple lower level example

multiple_lower_level_in_bileveljump.jl

using JuMP, BilevelJuMP

model = BilevelModel()

NLL = 3 # number of lower level (LL) models
GLL = [4, 5, 6] # generators in each lower level

@variable(Upper(model), 0 <= q[i in 1:NLL] <= 100)

# arbitrary upper constraint
@constraint(Upper(model), sum(i*q[i] for i in 1:NLL) <= 300)

# arbitray upper objective
@objective(Upper(model), Max, sum(q[i] for i in 1:NLL))

# there is only one lower level but you can write it
# as a blocked model, i.e., variable and constraints
# are only connected in their blocks

# so we start adding all variables of all LL
@variable(Lower(model), g[i in 1:NLL, j in 1:GLL[i]])

# now build similar constraints for all LL
for i in 1:NLL
    @constraint(Lower(model), sum(g[i, j] for j in 1:GLL[i]) == 100)
    @constraint(Lower(model), g[i, 1] <= q[i])
    @constraint(Lower(model), [j in 1:GLL[i]], g[i, j] <= 40)
    @constraint(Lower(model), [j in 1:GLL[i]], g[i, j] >= 0)
end

# the objective is little more complicated
# because we need a single objective
# but we can do it iteratively if we use @expressions

# initialize an empty objective
obj = @expression(model, 0.0)

# now add to objective for each LL
for i in 1:NLL
    obj = @expression(model,
        obj +
        sum(i*j*g[i, j] for j in 1:GLL[i])
    )
end

@objective(Lower(model), Min, obj)

# now you can optimize
# all `mode`s should do the exact same reformulations as if
# you had actually defined completely independent LL
# except StrongDualityMode, which will still give a valid
# MPEC formuation, though not the same as you would have if
# you could define problem independently

Thank you for providing this example! I tried to run it and got the following warning and error. After I added "local" in front of "obj = @expression(model, 0.0)", the warning went away, but the error persisted.

┌ Warning: Assignment to obj in soft scope is ambiguous because a global variable by the same name exists: obj will be treated as a new local. Disambiguate by using local obj to suppress this warning or global obj to assign to the existing global variable.
└ @ ~/JuliaProjects/Multiple_followers_example:40

ERROR: LoadError: UndefVarError: obj not defined

Do you have any suggestions on how to solve this error? Thank you very much.

I see, this is a Julia issue.
If you paste this code in the Julia REPL as is, it will work.
But if you include("this_file.jl") it will return such error.

You can add all the code inside a function like this:

using JuMP, BilevelJuMP

function my_funtion()
    model = BilevelModel()
    # the rest of the code goes here
end

my_funtion()

this will solve the scope issue.

Thank you for your response, Joaquim. It seems to be working now.

I have a doubt though. The way the code is set up it seems like it might be adding all lower-level objectives, resulting in a single lower-level objective, other than 3 separate lower objectives. All 12 constraints are added to that single lower-level program created. Although the optimal solution may be verified by some other solver that supports multiple lower-level programs, it is sometimes the case with specific formulations that adding all lower-level objectives and creating only one lower-level program may result in the same optimal solution as the bilevel program with the 3 lower-level programs. More specifically, I have tried:

using JuMP, BilevelJuMP

function my_funtion()
model = BilevelModel()
# the rest of the code goes here
print(obj)
end

my_funtion()

and I get:

g[1,1] + 2 g[1,2] + 3 g[1,3] + 4 g[1,4] + 2 g[2,1] + 4 g[2,2] + 6 g[2,3] + 8 g[2,4] + 10 g[2,5] + 3 g[3,1] + 6 g[3,2] + 9 g[3,3] + 12 g[3,4] + 15 g[3,5] + 18 g[3,6]

It seems to me like lower-level objectives are just added on top of each other. What do you think? Thank you.

You are correct. All lower levels are added to the same problem.

As long as they don't share variables that are not upper level variables, this is not an issue.

Thank you for your response, Joaquim.

I am personally not aware of a specific theory proving that when the lower-level programs do not share their variables, i.e. there is no assumed competition between the followers of the game, then the original bilevel program is equivalent to a bilevel program with a single-lower level program, that is the sum of the objectives of the lower-level programs with all the constraints of the initial lower-level programs. If you have such a reference, please share.

I am not sure if this might be the case with this particular example, it is possible, but I can't say for a fact that this would generalize to any bilevel program, especially if the followers have different forms of objectives or different weights in similar objectives. Saying that the two aforementioned bilevel programs are always equivalent in terms of an MPEC solver is almost like saying that solving the first-order (stationarity) condition of the sum of objectives (along with the other KKT conditions) is equivalent to solving the system of NLL stationarity conditions of all lower-level objectives. I do not know if something like that would be true in general, even if it happens to be the case here due to problems' symmetries.

Looking forward to hearing your thoughts. Best wishes!

If a decision variable appears in two different follower problems it must be a leader decision variable.
If you are in this situation (which you seem to be), you are fine. simply because the lower lever will decouple in blocks and the KKT of all the blocks together is equivalent to the KKT of all of them separately.

Thank you for your response. If you have a reference (paper) handy that proves that equivalence please do share as it is of great interest to me.

Do you think that applies only to linear lower-level program cases or also to quadratic lower-level programs that might contain objective terms such as x^2 or x*p (x: lower-level variable of the particular program, p: upper-level variable)?

Once again, thank you for your response!