Giter Club home page Giter Club logo

Comments (4)

odow avatar odow commented on June 4, 2024

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)
image

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.

from jump.jl.

odow avatar odow commented on June 4, 2024

I took another look at this.

Here's @profview add_soc_variables(100_000)

image

Looks good. Most time is spend in @constraint

Here's @proview add_soc(100_000)

image

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.

from jump.jl.

odow avatar odow commented on June 4, 2024

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

from jump.jl.

odow avatar odow commented on June 4, 2024

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.

from jump.jl.

Related Issues (20)

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.