Issues solving a bilevel optimization with binary variables

Specific Domains Optimization (Mathematical)
,
1

I’m new using Julia to solve my nonlinear mixed integer bilevel model, so I have a model in JuMP using BilevelJuMP with binary and continuous variables at the lower and upper level and with non-linear [non quadratic] constraints and objectives in the two levels.

a. Is there a way for BilevelJuMP to accept nonlinear objectives and constraints not only in the upper level, but also in the lower? I’ve been using the Ipopt solver, but it doesn’t support discrete variables.

b. For the above case, trying another way to solve, I have linearized my objective and constraints in both levels, making it a linear mixed integer bilevel model. I’m using the CPLEX 20.1 solver in Julia 1.9.3.

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

I have installed and set the CPLEX_STUDIO_BINARIES environment variable and run Pkg.add(“CPLEX”) without any issue, but when I try to optimize the model, it doesn’t work, I get the following error message: Would you have any suggestions on how to solve the issue?

Constraints of function MathOptInterface.SingleVariable in the Set MathOptInterface.ZeroOne are not implemented

Stacktrace:
[1] error(::String, ::Type, ::String, ::Type, ::String)
@ Base .\error.jl:44
[2] supported_constraints(con_types::Vector{Tuple{DataType, DataType}})
@ Dualization C:\Users\kchuq.julia\packages\Dualization\wDRnB\src\supported.jl:9
[3] dualize(primal_model::MathOptInterface.Utilities.CachingOptimizer{MathOptInterface.AbstractOptimizer, MathOptInterface.Utilities.UniversalFallback{MathOptInterface.Utilities.GenericModel{Float64, MathOptInterface.Utilities.ModelFunctionConstraints{Float64}}}}, dual_problem::Dualization.DualProblem{Float64, MathOptInterface.Utilities.GenericModel{Float64, Dualization.DualizableModelFunctionConstraints{Float64}}}, dual_names::Dualization.DualNames, variable_parameters::Vector{MathOptInterface.VariableIndex}, ignore_objective::Bool)
@ Dualization C:\Users\kchuq.julia\packages\Dualization\wDRnB\src\dualize.jl:50
[4] #dualize#9
@ C:\Users\kchuq.julia\packages\Dualization\wDRnB\src\dualize.jl:12 [inlined]
[5] dualize
@ C:\Users\kchuq.julia\packages\Dualization\wDRnB\src\dualize.jl:4 [inlined]
[6] build_bilevel(upper::MathOptInterface.Utilities.CachingOptimizer{MathOptInterface.AbstractOptimizer, MathOptInterface.Utilities.UniversalFallback{MathOptInterface.Utilities.GenericModel{Float64, MathOptInterface.Utilities.ModelFunctionConstraints{Float64}}}}, lower::MathOptInterface.Utilities.CachingOptimizer{MathOptInterface.AbstractOptimizer, MathOptInterface.Utilities.UniversalFallback{MathOptInterface.Utilities.GenericModel{Float64, MathOptInterface.Utilities.ModelFunctionConstraints{Float64}}}}, link::Dict{MathOptInterface.VariableIndex, MathOptInterface.VariableIndex}, upper_variables::Vector{MathOptInterface.VariableIndex}, mode::BilevelJuMP.SOS1Mode{Float64}, upper_var_lower_ctr::Dict{MathOptInterface.VariableIndex, MathOptInterface.ConstraintIndex}; copy_names::Bool, pass_start::Bool)
@ BilevelJuMP C:\Users\kchuq.julia\packages\BilevelJuMP\YP5EH\src\moi.jl:287
[7] optimize!(model::BilevelModel; lower_prob::String, upper_prob::String, bilevel_prob::String, solver_prob::String, file_format::MathOptInterface.FileFormats.FileFormat)
@ BilevelJuMP C:\Users\kchuq.julia\packages\BilevelJuMP\YP5EH\src\jump.jl:387
[8] optimize!(model::BilevelModel)
@ BilevelJuMP C:\Users\kchuq.julia\packages\BilevelJuMP\YP5EH\src\jump.jl:351
[9] top-level scope
@ In[70]:1

thanks

2

Hi @kiki, welcome to the forum!

Unfortunately, BilevelJuMP doesn’t support binary variables in the lower-level problem. It should probably throw a nicer error explaining this. (I’ve opened an issue: Issues · joaquimg/BilevelJuMP.jl · GitHub)

Even if you fix that, you won’t be able to use CPLEX because it doesn’t support nonlinear programs.

If you can post a minimal example of your problem @joaquimg (the author of BilevelJuMP) might be able to point you in a better direction.

Oscar

3

Hi, I have a problem with the code belay, initially it was a bilevel mixed integer nonlinear problem, but it has been linearized, the variable a[i,j] has been used to linearize X[j]*y[i, j] in this model, but after trying to optimize I get the error: Constraints of function MathOptInterface.SingleVariable in the Set MathOptInterface.ZeroOne are not implemented. Any idea how can i fixed it? Thanks

code

4

Requiring Binaries in the lower level is problematic because solution methods scale very very poorly.

BilevelJuMP can handle binaries in the lower level as an experimental feature:
MibS: Example 1 (Experimental feature) · BilevelJuMP.jl (this will not scale to large scale problems even when the feature is no experimental anymore).