Slow solution of large LPs w/o direct model

[pkienscherf]

As discussed here: https://discourse.julialang.org/t/jump-optimize-used-two-much-time-and-memory-to-solve-a-cplex-model-do-anyone-knows-why/77966/9 I have an issue with long solution times when not using a direct model. The original problem that I cannot show here takes roughly 600s to solve as a regular model vs roughly 1.1s as a direct model. I have observed similar behavior (60s vs. 1.7s) in the following MWE (even if not for the same reason, I suppose it's still interesting):

using JuMP
using CPLEX

A = 1:100
T = 1:1000

m = Model(CPLEX.Optimizer)

@variables m begin
    0 <= x[A, T] <= 2
end

@constraints m begin
    [a in A[2:end], t in T], x[a ,t] >= 0.5 * x[a-1, t]
    [a in A, t in T[2:end]], x[a, t] - x[a, t-1] >= -1
    [a in A, t in T[2:end]], - x[a, t] + x[a, t-1] <= 1
end

@objective(m, Min, sum(x))

@time optimize!(m)

My setup is as follows:

Julia Version 1.7.2
Commit bf53498635 (2022-02-06 15:21 UTC)
Platform Info:
  OS: macOS (x86_64-apple-darwin19.5.0)
  CPU: Intel(R) Core(TM) i5-5350U CPU @ 1.80GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-12.0.1 (ORCJIT, broadwell)

  [6e4b80f9] BenchmarkTools v1.3.1
  [a076750e] CPLEX v0.9.1
  [a93c6f00] DataFrames v1.3.2
  [31c24e10] Distributions v0.25.53
  [2e9cd046] Gurobi v0.11.0
  [7073ff75] IJulia v1.23.2
  [b6b21f68] Ipopt v1.0.2
  [4076af6c] JuMP v1.0.0
  [8314cec4] PGFPlotsX v1.4.1
  [91a5bcdd] Plots v1.27.4
  [014a38d5] QuadraticToBinary v0.4.0
  [295af30f] Revise v3.3.3
  [f3b207a7] StatsPlots v0.14.33
  [0c5d862f] Symbolics v4.3.1
  [fdbf4ff8] XLSX v0.7.9
  [e88e6eb3] Zygote v0.6.37
  [10745b16] Statistics

[odow]

I found the culprit:

It's a recent change from JuMP to push names to the solver. I have a fix incoming that results in:

julia> @time main(CPLEX.Optimizer; n = 100, m = 1000, use_direct_model = true)
  1.654135 seconds (10.97 M allocations: 531.884 MiB, 16.13% gc time)
OPTIMAL::TerminationStatusCode = 1

julia> @time main(CPLEX.Optimizer; n = 100, m = 1000, use_direct_model = false)
  2.546805 seconds (14.66 M allocations: 1023.582 MiB, 28.79% gc time)
OPTIMAL::TerminationStatusCode = 1

[mlubin]

Just to be sure, the direct_model version does not pass names?

[odow]

Okay, here's the complicated bit I didn't mention:

• direct_model does pass names, but direct_model does add_variable, set VariableName, add_variable...
• Model adds all of the variables, and then calls set VariableName for each of the variables.

I guess there is something internally in CPLEX for why the direct_model way is fast, and the Model was is slow? That doesn't really seem fixable, so I opted to just skip names. That reverts us to what used to happen (pre MOI@0.10), and people using direct_model can opt-in to passing names.

[odow]

The other option is to write a new MOI.copy_to instead of using MOI.Utilities.default_copy_to, but that's a lot more work.

[mlubin]

Opt in is ok, just document the performance quirk for future reference.

[odow]

How is:
https://github.com/jump-dev/CPLEX.jl/pull/393/files#diff-ef373163d7f4974d49959bee1af7409c21eb5e14088e77d6dca1fb23e57e34aeR143-R152

[mlubin]

That's good for users. We should also document for developers (in case someone wants to write a custom MOI.copy_to) that we observed that add_variable, then set VariableName then add_variable is faster than adding everything in batch then setting names in batch.