Slow variable construction when using JuMP

[coroa]

Summary: Constructing bounded variables from JuMP using LQOI is prohibitively slow due to constraint conflict checks in LQOI and excessive model updates induced by single variable additions and updates. Adapting the implementation of the JuMP.variable macro together with an implementation for addconstraints! in LQOI, seems to recover the speed of MPB. What are the plans to address this?

Disclaimer: All test are on julia 0.6.

using BenchmarkTools
using .Profile
using JuMP
import JuMPMPB # release-0.18 branch renamed to be able to use in parallel
using Gurobi
using MathOptInterface; const MOI=MathOptInterface

function run_moi_direct(n)
  m = JuMP.direct_model(Gurobi.Optimizer(LogToConsole=false))
  @variable m x[i=1:n] <= i 
  JuMP.optimize(m)
end

function run_moi_caching(n)
  m = JuMP.Model(with_optimizer(Gurobi.Optimizer, LogToConsole=false))
  @variable m x[i=1:n] <= i 
  JuMP.optimize(m)
end

function run_mpb(n)
  m = JuMPMPB.Model(solver=GurobiSolver(LogToConsole=false))
  JuMPMPB.@variable m x[i=1:n] <= i 
  JuMPMPB.solve(m)
end

The old MathProgBase based JuMP:

run_mpb(1)
@btime run_mpb(10^4)
# 17.638 ms (29775 allocations: 3.93 MiB)

Direct mode as well as caching mode of MOI based JuMP take about 40 times as
long (in the case of an additional lowerbound this becomes 80 times)

run_moi_direct(1) @btime run_moi_direct(10^4)
# 683.307 ms (533812 allocations: 24.35 MiB)

run_moi_caching(1)
@btime run_moi_caching(10^4)
# 736.283 ms (1053901 allocations: 44.24 MiB)

Profile.clear()
@profile run_moi_direct(10^4)
Profile.print(mincount=100)
# 789 ./REPL[6]:3; run_moi_direct(::Int64)
#  789 ...6/JuMP/src/macros.jl:182; macro expansion
#   705 ...uMP/src/variables.jl:521; addvariable(::JuMP.Model, ::Ju...
#    700 ...MP/src/variables.jl:334; setupperbound(::JuMP.VariableR...
#     644 ...s/singlevariable.jl:101; addconstraint!(::Gurobi.Optim...
#      644 ...s/singlevariable.jl:95; __check_for_conflicting__(::G...
#       633 ...s/singlevariable.jl:68; __check_for_conflicting__(::G...
#        595 ./reduce.jl:573; any(::Base.##138#139{MathOp...
#         299 ./dict.jl:567; skip_deleted(::Dict{MathOpt...

The profile shows that 4/5 of the time is spent in LQOI's __check_for_conflicting__ function when setting the upperbound. It seems there should be a way to bypass that check (we're
talking about setting a variable bound) or do it once for the bunch of
variables.

The second big chunk of time (nearly 9/10) is actually spent on updating the
lower level gurobi model twice for each variable, i.e. the separate creation and
updating of the upperbound.

# after commenting: __check_for_conflicting__ at LQOI/singlevariable.jl:101

@btime run_moi_direct(10^4)
# 130.537 ms (483812 allocations: 23.59 MiB)

Profile.clear()
@profile run_moi_direct(10^5)
Profile.print(mincount=100)

# 6201 ./REPL[7]:3; run_moi_direct(::Int64)
#  6201 ...6/JuMP/src/macros.jl:182; macro expansion
#   134  ./strings/io.jl:91; #print_to_string#231(::Void, :...
#   4178 ...MP/src/variables.jl:516; addvariable(::JuMP.Model, ::Ju...
#    4156 ...MP/src/variables.jl:160; Type
#     4103 ...ce/src/variables.jl:86; addvariable!(::Gurobi.Optimizer)
#      104  .../src/MOIWrapper.jl:303; add_variables!
#      3998 ...i/src/grb_model.jl:100; update_model!(::Gurobi.Model)
#   1770 ...MP/src/variables.jl:521; addvariable(::JuMP.Model, ::Ju...
#    1719 ...MP/src/variables.jl:334; setupperbound(::JuMP.Variable...
#     1615 ...s/singlevariable.jl:103; addconstraint!(::Gurobi.Optim...
#      1516 .../src/MOIWrapper.jl:114; change_variable_bounds!(::Gu...
#       1514 ...i/src/grb_model.jl:100; update_model!(::Gurobi.Model)

If one neglects the storage bit, the @variable JuMP macro is expanded to

for i = 1:n
    (JuMP.addvariable)(m, (JuMP.buildvariable)(_error, (JuMP.VariableInfo)(false, NaN, true, i, false, NaN, false, NaN, false, false)), (JuMP.string)("x", "[", i, "]"))
end

or

function run_moi_single(n)
  m = JuMP.direct_model(Gurobi.Optimizer(LogToConsole=false))
  for i = 1:n
      index = MOI.addvariable!(m.moibackend)
      MOI.addconstraint!(m.moibackend, MOI.SingleVariable(index), MOI.LessThan(convert(Float64,i)))
      # Plus setting the name, but let's neglect that for now
  end
end

run_moi_single(1)
@btime run_moi_single(10^4)
# 107.721 ms (286960 allocations: 16.08 MiB)

One could imagine to have JuMP expand it instead to

function run_moi_vector(n)
  m = JuMP.direct_model(Gurobi.Optimizer(LogToConsole=false))
  index = MOI.addvariables!(m.moibackend, n)
  MOI.addconstraints!(m.moibackend, MOI.VectorOfVariables(index), MOI.LessThan.(convert.(Float64,1:n)))
  # Plus setting the name, but let's neglect that for now
end

as proposed in jump-dev/MathOptInterface.jl#63 (comment) .
And provide an LQOI implementation for the
addconstraints!(::SolverInstance,::Vector{F},::Vector{S})
as the POC in coroa@d085429 .

Then one could recover the MPB speed:

run_moi_vector(1)
@btime run_moi_vector(10^4)
# 17.343 ms (63405 allocations: 2.92 MiB)

Is this the plan? Are there other plans? Does

LinQuadOptInterface.jl/src/constraints/vectorofvariables.jl

Line 18 in 4f75448

function MOI.addconstraint!(model::LinQuadOptimizer, func::VecVar, set::S) where S <: VecLinSets

already provide this and I just don't see how?

Are the JuMP macros being adapted?

Sorry, this has become somewhat lengthy, it started exploratorily and turned
into something interesting on the way.

[odow]

Hi @coroa,

Thanks for this pretty impressive write-up. I don't have time to address all your points, but I'll layout my initial thoughts and come back to this in the weekend.

To date, the development of JuMP/MOI/LQOI/the solver wrappers has focused on functionality. It is likely that at the release of JuMP 0.19 will be slower than JuMP 0.18. However, once the API's settle down, we can start to optimize speed. The 40x+ slow-down is a deal-breaker for my work and @joaquimg's so this will definitely be addressed at some point.

That said, there are a few fixes that can make improvements:

• In Gurobi.jl, we should move all of the update_model! lines (e.g., like this) from the end of the set functions to the start of the get functions. Presumably calling update_model! on a model with no changes is a no-op in Gurobi. However, if this has some overhead we could store a flag indicating whether we needed to update the model before letting the user query some part of it.
• JuMP should definitely use the MOI.addvariables!(model, n) call. However, this is likely to be a little difficult in some cases, for example, if the conditional syntax is used. I am not aware of any current efforts to adapt the JuMP macros to this. As I said above, the current focus has just been on getting something working. (cc @mlubin.)
• LQOI should definitely implement MOI.addconstraints for variable bounds. PR's welcome :)
• I want to remove the VectorOfVariables-in-Set functionality in favour of bridges (see Add bridges #34).
• __check_for_conflicting__ was added to prevent incorrect behaviour. It wasn't written with performance in mind. PR's to improve this would be great!