Increase performance of SOC constraints

[chrhansk]

Welcome to JuMP! You can use this Github issue to suggest a new feature for JuMP.

Is your feature request related to a problem? Please describe.

I noticed that a model containing several SOC constraints was built rather slowly. As an example, consider this benchmark:

using JuMP
using Profile
import Gurobi

function add_linear()
    model = Model(Gurobi.Optimizer)

    x = @variable(model, x)
    y = @variable(model, y)
    z = @variable(model, z)

    for i in 1:100
        @constraint(model, x + y + z <= 1)
    end
end

function add_soc()
    model = Model(Gurobi.Optimizer)

    x = @variable(model, x)
    y = @variable(model, y)
    z = @variable(model, z)

    vec = [1, y, z]

    for i in 1:100
        @constraint(model, [x; vec] in SecondOrderCone())
    end
end

@profile add_linear()

Profile.print(format=:flat)

@profile add_soc()

Profile.print(format=:flat)

By running the benchmark I see

[...]
   182       182 @JuMP/src/constraints.jl                                 713 add_constraint(model::Model, con::ScalarConstraint{AffExpr, MathOptInterface.LessThan{Float64}}, name::String)                     
[...]
  3368       428 @JuMP/src/constraints.jl                                 713 add_constraint(model::Model, con::VectorConstraint{AffExpr, MathOptInterface.SecondOrderCone, VectorShape}, name::String)
[...]

As seen here, adding an SOC constraint takes an order of magnitude more time than adding a linear one.

Describe the solution you'd like

I realize that SOC constraints may be more complex for solvers than linear ones, but I am less clear on why the addition of the constraints takes so noticeably long. I would appreciate if you could somewhat tweak the performance.

[odow]

Consider

using JuMP
using BenchmarkTools
import Gurobi

const GRB_ENV = Gurobi.Env()
grb_optimizer() = Gurobi.Optimizer(GRB_ENV)

function add_linear(N)
    model = Model(grb_optimizer)
    @variable(model, x)
    @variable(model, y)
    @variable(model, z)
    for _ in 1:N
        @constraint(model, x + y + z <= 1)
    end
    return model
end

function add_soc(N)
    model = Model(grb_optimizer)
    @variable(model, x)
    @variable(model, y)
    @variable(model, z)
    vec = [1, y, z]
    for _ in 1:N
        @constraint(model, [x; vec] in SecondOrderCone())
    end
    return model
end

function add_soc_variables(N)
    model = Model(grb_optimizer)
    @variable(model, x)
    @variable(model, y)
    @variable(model, z)
    for _ in 1:N
        @constraint(model, [x, y, z] in SecondOrderCone())
    end
    return model
end

@benchmark add_linear(100)
@benchmark add_soc(100)
@benchmark add_soc_variables(100)

julia> @benchmark add_linear(100)
BenchmarkTools.Trial: 5224 samples with 1 evaluation.
 Range (min … max):  855.013 μs …   6.484 ms  ┊ GC (min … max): 0.00% … 50.29%
 Time  (median):     920.186 μs               ┊ GC (median):    0.00%
 Time  (mean ± σ):   953.208 μs ± 260.691 μs  ┊ GC (mean ± σ):  1.10% ±  3.54%

       ▂▄▇██▇▆▅▄▄▃▁▂▂▂▂▁▁▁▁▁                                    ▂
  ▄▄▁▅███████████████████████████▇█▆▆▆▇▆▇▃▅▅▆▅▄▆▅▆▄▃▅▆▃▆▅▁▅▅▃▅▄ █
  855 μs        Histogram: log(frequency) by time       1.26 ms <

 Memory estimate: 157.70 KiB, allocs estimate: 3528.

julia> @benchmark add_soc(100)
BenchmarkTools.Trial: 1146 samples with 1 evaluation.
 Range (min … max):  3.405 ms …   9.597 ms  ┊ GC (min … max): 0.00% … 48.91%
 Time  (median):     4.417 ms               ┊ GC (median):    0.00%
 Time  (mean ± σ):   4.355 ms ± 468.127 μs  ┊ GC (mean ± σ):  0.52% ±  3.38%

    ▁▁ ▁▂▂                          ▂▂▂ ▁▆██▇▅▄▄▄▄▃▂ ▁        ▁
  ▄▇████████▇██▆█▇▇▆▇▄█▅▆▄▁▆▆▁▆▄▆▅▅██████████████████████▁▁▁▅ █
  3.4 ms       Histogram: log(frequency) by time      4.86 ms <

 Memory estimate: 242.95 KiB, allocs estimate: 4631.

julia> @benchmark add_soc_variables(100)
BenchmarkTools.Trial: 3678 samples with 1 evaluation.
 Range (min … max):  1.211 ms …   7.100 ms  ┊ GC (min … max): 0.00% … 51.24%
 Time  (median):     1.324 ms               ┊ GC (median):    0.00%
 Time  (mean ± σ):   1.355 ms ± 245.645 μs  ┊ GC (mean ± σ):  0.60% ±  2.75%

          ▁█▇▅▃                                                
  ▂▁▁▁▂▃▄▅██████████▇▇▇▆▆▅▄▄▄▄▃▃▃▃▃▃▃▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂ ▃
  1.21 ms         Histogram: frequency by time        1.69 ms <

 Memory estimate: 111.09 KiB, allocs estimate: 2928.

The underlying issue it that Gurobi does not support VectorAffineFunction{Float64}-in-SecondOrderCone so the bridges need to get involved.

Here's:

import ProfileView
@profview add_soc(100)

The time is in supports_bridging_constraint which is not type stable.

The add_soc_variables creates VectorOfVariables-in-SecondOrderCone which Gurobi does support and it is much faster.

The time to add 100,000 constraints is also negligible. add_soc_variables is even a bit faster than add_linear, and add_soc, while perhaps 2X slower, is still not a bottleneck.

julia> GC.gc(); @time add_linear(100_000);
  0.077155 seconds (1.40 M allocations: 101.363 MiB, 17.74% gc time)

julia> GC.gc(); @time add_soc(100_000);
  0.128777 seconds (1.80 M allocations: 143.006 MiB, 26.64% gc time)

julia> GC.gc(); @time add_soc_variables(100_000);
  0.032610 seconds (802.13 k allocations: 55.587 MiB)

julia> GC.gc(); @time add_linear(100_000);
  0.073181 seconds (1.40 M allocations: 101.363 MiB, 15.95% gc time)

julia> GC.gc(); @time add_soc(100_000);
  0.125340 seconds (1.80 M allocations: 143.006 MiB, 26.69% gc time)

julia> GC.gc(); @time add_soc_variables(100_000);
  0.040289 seconds (802.13 k allocations: 55.587 MiB)

I don't know if there's much we can or should do here.

[odow]

I took another look at this.

Here's @profview add_soc_variables(100_000)

Looks good. Most time is spend in @constraint

Here's @proview add_soc(100_000)

Most time is spent creating a vector of AffExpr in the [x; vec] line. Particularly the cost of creating a new OrderedDict for each element.

[odow]

@chrhansk can you post a benchmark of your actual problem that is slow to build? Otherwise I will close this issue.

[odow]

Closing as won't-fix.

If you can post an example where this is a problem, please comment and I will re-open. You could also post on https://discourse.julialang.org/c/domain/opt/13 if you want some advice on improving the speed of problem construction.