Question on BilevelJuMP model concise formulation

Specific Domains Optimization (Mathematical)
, ,
1

I am trying to break a BilevelJuMP model into smaller functions (similar to what is recommended for a JuMP model when working with complex problems). My question is whether the models written below are all interpreted as the same by the BilevelJuMP package:

Base formulation: (from BilevelJuMP GitHub page)

using JuMP, BilevelJuMP, Gurobi

model = BilevelModel(Gurobi.Optimizer, mode = BilevelJuMP.SOS1Mode())

@variable(Lower(model), x)
@variable(Upper(model), y)

@objective(Upper(model), Min, 3x + y)
@constraints(Upper(model), begin
    x <= 5
    y <= 8
    y >= 0
end)

@objective(Lower(model), Min, -x)
@constraints(Lower(model), begin
     x +  y <= 8
    4x +  y >= 8
    2x +  y <= 13
    2x - 7y <= 0
end)

optimize!(model)

objective_value(model) # = 3 * (3.5 * 8/15) + 8/15 # = 6.13...
value(x) # = 3.5 * 8/15 # = 1.86...
value(y) # = 8/15 # = 0.53...

Representation 1: (Breaking into different functions)

using JuMP, BilevelJuMP, Gurobi

function add_var(model)
    @variable(Lower(model), x)
    @variable(Upper(model), y)
    return
end

function add_cons(model)
     x = model[:x]
     y = model[:y]
     @constraints(Upper(model), begin
          x <= 5
          y <= 8
          y >= 0
      end)
      @constraints(Lower(model), begin
           x+y <= 8
           4x+y >= 8
           x+y <=13
           2x-7y <= 0
       end)
       return
end
    
function add_objectives(model)
    x = model[:x]
    y = model[:y]
    @objective(Upper(model), Min, 3x+y)
    @objective(Lower(model), Min, -x)
     return
end

function solve()
    model = BilevelModel(Gurobi.Optimizer, mode=BilevelJuMP.SOS1Mode())
    add_var(model)
    add_cons(model)
    add_objectives(model)
    optimize!(model)
    println(objective_value(model))
    println(value(model[:x]))
    println(value(model[:y]))
end

solve()

Are representation 1 and base formulation equivalent? I get the same solution from both; however, my main concerns are the lines x=model[:x] and y=model[:y] because variables and constraints here are attached to the lower- and upper-level model separately, I wanted to confirm if this is indeed a correct way to write the model.

If they are equivalent, can I further split the functions for lower and upper variables, constraints, and objectives? Example:

function add_var_lower(model)
    @variable(Lower(model), x)
    return
end

function add_var_upper(model)
    @variable(Upper(model), y)
    return
end

function add_cons_lower(model)
     x = model[:x]
     y = model[:y]
      @constraints(Lower(model), begin
           x+y <= 8
           4x+y >= 8
           x+y <=13
           2x-7y <= 0
       end)
       return
end

# and so on...and then I will have solve function as:


function solve()
    model = BilevelModel(Gurobi.Optimizer, mode=BilevelJuMP.SOS1Mode())
    add_var_lower(model)    #lower-level variables
    add_var_upper(model)   #upper-level variables
    add_cons_lower(model)  #lower-level constraints
    add_cons_upper(model) #upper-level constraints
    add_objective_lower(model) #lower-level objective
    add_objective_upper(model) #upper-level objective
    optimize!(model)
    println(objective_value(model))
    println(value(model[:x]))
    println(value(model[:y]))
end

solve()

I tried this and it still gives me the same solution; however, again, I want to confirm whether it is safe to do so? Thanks.

2

I haven’t tried, but does this work?

# Instead of x = model[:x]
x = Lower(model)[:x]

If so, it might be preferred to look up the variable from the correct level.

1 Like
3

Yes, this also gives me the same solution.

function add_var(model)
    @variable(Lower(model), x)
    @variable(Upper(model), y)
    return
end

function add_cons(model)
     x = Lower(model)[:x]
     y = Upper(model)[:y]
     @constraints(Upper(model), begin
          x <= 5
          y <= 8
          y >= 0
      end)
      @constraints(Lower(model), begin
           x+y <= 8
           4x+y >= 8
           x+y <=13
           2x-7y <= 0
       end)
       return
end
    
function add_objectives(model)
    x = Lower(model)[:x]
    y = Upper(model)[:y]
    @objective(Upper(model), Min, 3x+y)
    @objective(Lower(model), Min, -x)
     return
end

function solve_new()
    model = BilevelModel(Gurobi.Optimizer, mode=BilevelJuMP.SOS1Mode())
    add_var(model)
    add_cons(model)
    add_objectives(model)
    optimize!(model)
    println(objective_value(model))
    println(value(Lower(model)[:x]))
    println(value(Upper(model)[:y]))
end

solve_new()

This definitely feels more safe since here I am accessing the variables from the level that I assigned them to; however, is this always the correct way for any general bilevel problem that I might write using the BilevelJuMP package? I just want to be sure before I start writing code this way :sweat_smile:.
Another question: while accessing variable values (solution), do I need to write value(Lower(model)[:x]) (see solve_new() function above) or does value(model[:x]) suffice? They both return the same value for the problem used in the code shown above.

4

@joaquimg is the person to answer this, but I test this as follows:

  • Can you have a variable called x in the lower and in the upper? If so, I would stick with accessing the variable form the model you defined it in. If not, then it should be safe to use model[:x], which internally probably checks what model you defined it in and returns that.
1 Like
5

That makes sense. I usually have a subset of variables that feature in both level constraints, so I guess the safest way would be to always access all my variables (irrespective of if they feature in one or both levels) from the level they were assigned to. I will see what @joaquimg suggests before I start refactoring my code. Thanks a lot!

1 Like
6

Your code looks great.
As of now model[:x] and Lower(model)[:x] should be the same. BilevelJuMP is caching everything in the same objdict.
I haven’t given much thought to this part of the API and don’t have strong feeling as of now.
Feel free to open an issue or PR to start a discussion.

1 Like