Normal execution path of CLP involves exception throwing/catching

[mabokhamis]

The normal execution path of using Clp to solve a linear program through JuMP involves throwing and catching an exception. In particular, an exception is always thrown here https://github.com/jump-dev/MathOptInterface.jl/blob/ac22378a3dd310603ced6ccf0141f16d73cae091/src/variables.jl#L37 and is caught here (or in a similar place in the same file) https://github.com/jump-dev/MathOptInterface.jl/blob/ac22378a3dd310603ced6ccf0141f16d73cae091/src/Utilities/cachingoptimizer.jl#L308 The exception handling can take up a significant portion of the overall optimization time, as shown by the benchmark below. Is there a way to avoid it?

using JuMP, Clp, MathOptInterface
using Profile, PProf

function test_clp(n::Int = 1000)
    for i = 1:n
        model = Model(Clp.Optimizer)
        set_optimizer_attribute(model, "LogLevel", 0)
        @variable(model, λ[1:3] ≥ 0.0)
        obj = @expression(model, sum(λ[jj] for jj in 1:3))
        @objective(model, Min, obj)
        @constraint(model, con[ii in 1:3],
                    sum(λ[jj] for jj in 1:3 if jj != ii) ≥ 1.0)
        optimize!(model)
        @assert termination_status(model) == MathOptInterface.OPTIMAL
        sol = value.(λ)
        obj_value = objective_value(model)
    end
end

test_clp(1000) # warmpup
Profile.init(n=Int(1e8), delay=0.002)
@pprof test_clp(1000)

[odow]

No, at present there is not way to avoid this. The logic of how and when to add variables to solvers is surprisingly complicated given the diversity of solvers. (There are some related issues: https://github.com/jump-dev/MathOptInterface.jl/issues/1156.)

To date, we have focused on functionality. One of the last items on our roadmap is fixing performance issues like this: https://jump.dev/JuMP.jl/stable/roadmap/#JuMP-1.0.

However: is this a bottleneck in your full code? Sure it's a lot for this problem, but that is only the optimize! call, and actually solving a 3 variable LP is trivial. For any real problems, the overhead of the try-catch is minimal.

p.s. I've moved this to MathOptInterface.

[mlubin]

Does this exception get thrown once or once for each variable? The latter would be worrying.

Are you really solving 3-variable LPs?

[odow]

I think it just gets thrown once. JuMP starts with the optimizer attached. It tries to add the variable, the optimizer gets reset. It gets built in the cache, and then it is copy_tod.

1156 suggests that we should probably start by building the cache, even if the solver supports incremental modification. That way incremental solvers can benefit from a fast copy_to. At present they just go the add_variable route, and never get called with copy_to. This is correct, but not the full story. See below.

Here's the workflow. JuMP starts with an outer EMPTY_OPTIMIZER, but there is an inner cache below the bridges that starts off ATTACHED:

julia> model = Model(Clp.Optimizer)
A JuMP Model
Feasibility problem with:
Variables: 0
Model mode: AUTOMATIC
CachingOptimizer state: EMPTY_OPTIMIZER
Solver name: Clp

julia> @variable(model, x)
x

julia> backend(model)
MOIU.CachingOptimizer{MOI.AbstractOptimizer,MOIU.UniversalFallback{MOIU.Model{Float64}}}
in state EMPTY_OPTIMIZER
in mode AUTOMATIC
with model cache MOIU.UniversalFallback{MOIU.Model{Float64}}
  fallback for MOIU.Model{Float64}
with optimizer MOIB.LazyBridgeOptimizer{MOIU.CachingOptimizer{Clp.Optimizer,MOIU.UniversalFallback{MOIU.Model{Float64}}}}
  with 0 variable bridges
  with 0 constraint bridges
  with 0 objective bridges
  with inner model MOIU.CachingOptimizer{Clp.Optimizer,MOIU.UniversalFallback{MOIU.Model{Float64}}}
    in state ATTACHED_OPTIMIZER
    in mode AUTOMATIC
    with model cache MOIU.UniversalFallback{MOIU.Model{Float64}}
      fallback for MOIU.Model{Float64}
    with optimizer Clp.Optimizer

However, when you call attach, it attempts to attach the outer cache:

julia> MOIU.attach_optimizer(model)

julia> backend(model)
MOIU.CachingOptimizer{MOI.AbstractOptimizer,MOIU.UniversalFallback{MOIU.Model{Float64}}}
in state ATTACHED_OPTIMIZER
in mode AUTOMATIC
with model cache MOIU.UniversalFallback{MOIU.Model{Float64}}
  fallback for MOIU.Model{Float64}
with optimizer MOIB.LazyBridgeOptimizer{MOIU.CachingOptimizer{Clp.Optimizer,MOIU.UniversalFallback{MOIU.Model{Float64}}}}
  with 0 variable bridges
  with 0 constraint bridges
  with 0 objective bridges
  with inner model MOIU.CachingOptimizer{Clp.Optimizer,MOIU.UniversalFallback{MOIU.Model{Float64}}}
    in state EMPTY_OPTIMIZER
    in mode AUTOMATIC
    with model cache MOIU.UniversalFallback{MOIU.Model{Float64}}
      fallback for MOIU.Model{Float64}
    with optimizer Clp.Optimizer

But, at this point it can't attach the inner cache, so it has to empty it (this is hitting the try).

Then when optimize! gets called, the inner cache is attached (fast) and the model is solved:

julia> optimize!(model)
Clp3002W Empty problem - 0 rows, 1 columns and 0 elements
Clp0000I Optimal - objective value 0
Clp0032I Optimal objective 0 - 0 iterations time 0.002

julia> backend(model)
MOIU.CachingOptimizer{MOI.AbstractOptimizer,MOIU.UniversalFallback{MOIU.Model{Float64}}}
in state ATTACHED_OPTIMIZER
in mode AUTOMATIC
with model cache MOIU.UniversalFallback{MOIU.Model{Float64}}
  fallback for MOIU.Model{Float64}
with optimizer MOIB.LazyBridgeOptimizer{MOIU.CachingOptimizer{Clp.Optimizer,MOIU.UniversalFallback{MOIU.Model{Float64}}}}
  with 0 variable bridges
  with 0 constraint bridges
  with 0 objective bridges
  with inner model MOIU.CachingOptimizer{Clp.Optimizer,MOIU.UniversalFallback{MOIU.Model{Float64}}}
    in state ATTACHED_OPTIMIZER
    in mode AUTOMATIC
    with model cache MOIU.UniversalFallback{MOIU.Model{Float64}}
      fallback for MOIU.Model{Float64}
    with optimizer Clp.Optimizer

We really need a flowchart of all the possible states that a caching optimizer can be in, and how it transitions to each state.

[mabokhamis]

Many thanks for your replies! We (relationalAI) have been using LP for database query optimization where we solve a large number of LPs, each of which corresponds to a candidate query plan. This is basically why this exception showed up on our benchmarks.

I indeed see the complexity in providing a unified interface for such a large number of solvers, as done in MathOptInterface/JuMP. As a side question: Do you think it would be feasible for us to communicate with Clp directly? Clp.jl at the moment doesn't seem to provide an interface independent of MOI, but will try to dig a bit in the code..

[odow]

Actually, there is a way around it if you are just formulating and solving simple LPs:

function test_clp2(n::Int)
    for i = 1:n
        optimizer = MOI.Utilities.CachingOptimizer(
            MOI.Utilities.UniversalFallback(MOI.Utilities.Model{Float64}()), 
            Clp.Optimizer(),
        )
        model = direct_model(optimizer)
        set_silent(model)
        @variable(model, λ[1:3] ≥ 0.0)
        obj = @expression(model, sum(λ[jj] for jj in 1:3))
        @objective(model, Min, obj)
        @constraint(model, con[ii in 1:3],
                    sum(λ[jj] for jj in 1:3 if jj != ii) ≥ 1.0)
        optimize!(model)
        @assert termination_status(model) == MOI.OPTIMAL
        sol = value.(λ)
        obj_value = objective_value(model)
    end
end

I get

julia> @time test_clp(1000)
  0.686145 seconds (2.57 M allocations: 177.704 MiB, 4.63% gc time)

julia> @time test_clp2(1000)
  0.351808 seconds (1.07 M allocations: 87.021 MiB, 3.84% gc time)

[odow]

There is also the C API if you want to avoid JuMP: https://github.com/jump-dev/Clp.jl/blob/master/src/gen/libclp_api.jl

[odow]

I forgot about this even easier way:

model = Model(Clp.Optimizer; bridge_constraints = false)

[mabokhamis]

I forgot about this even easier way:

model = Model(Clp.Optimizer; bridge_constraints = false)

Many thanks @odow ! This does indeed remove the exception :+1:

[odow]

Closed by #1254