Question on handling product of variables in BilevelJuMP

Specific Domains Optimization (Mathematical)
,
1

I have a bilevel model where my inner-level problem has terms in constraints and objective that are the product of an upper-level and a lower-level variable. For example,

using JuMP, BilevelJuMP, Gurobi

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

@variable(Lower(model), x <= 10)
@variable(Upper(model), y, Bin)

@objective(Upper(model), Min, 3x + y)

@objective(Lower(model), Min, -x*y)
@constraints(Lower(model), begin
     x +  y <= 8
    x*y >= 5
end)

optimize!(model)

Now, my questions are:

  1. I see that BilevelJuMP package can handle the product of variables in lower-level objective but not in lower-level constraints. Is there a way around it? My understanding is that since y is a parameter for the lower-level problem, it is an LP, and we can thus write its KKT condition as usual? Is the package not designed to handle it currently or is there any other reason?

  2. In the example above, I have a product of a binary and continuous variable, which can be linearized. So, is this what is recommended, i.e., should I linearize these terms and then re-write my lower problem? What if it was a product of two continuous variables? Even though y would still be a parameter for the lower-level problem making it an LP, what would be the suggested way to use the BilevelJuMP package for such problems?

Looking for more insights on this. Thanks!

2

cc @joaquimg

Is there a way around it?

My guess is that BilevelJuMP can support it, but probably not if you use Gurobi and SOS. Joaquim can probably say more.

I have a product of a binary and continuous variable, which can be linearized. So, is this what is recommended, i.e., should I linearize these terms and then re-write my lower problem?

Almost certainly, yes.

1 Like
3

BilevelJuMP is not able to solve problems with quadratic constraints in the lower level. Hence, for now, the answer is no. However, BilevelJuMP supports Second Order Cone constraints in the lower level, so you might be able to reformulate in some special (convex) cases.
But, as you noticed, there might be hope in the future since the product is between a lower level and upper level variables.

2 Likes
4

Got it. Thanks for the clarification.