Very slow performance when modifying and querying a model with JuMP

Specific Domains Optimization (Mathematical)
,
1

Hello,

I have a question about the modifications and queries of a model with jump. If I use a jump model with set_objective_coefficient and set_normalized_coefficient, the computational times are 25 times slower than with a direct model.

Also, using normalized_coefficient is very slow (about 7 to 9 seconds on my machine to query 10000 coefficients).

I have uploaded a code to this message illustrating the problem. The output that I have is :

Set objective and constraint coefficients with model
 24.952014 seconds (20.13 M allocations: 1.075 GiB, 1.06% gc time, 0.06% compilation time)
Set objective and constraint coefficients with direct model
  1.001638 seconds (50.12 M allocations: 920.339 MiB, 3.52% gc time)
Read constraint coefficients with model
  7.129312 seconds (1.46 M allocations: 15.767 GiB, 5.58% gc time)
Read constraint coefficients with direct model
  8.741839 seconds (1.66 M allocations: 16.893 GiB, 5.37% gc time, 0.66% compilation time)

details: macos 15.0.01, julia 1.11.1, JuMP 1.23.4, Gurobi.jl 1.4.0, Gurobi 12.0

Remarks : using HiGHS, the modifications with the direct model are not much more efficient and the queries with the direct model are sky rocketing:

Set objective and constraint coefficients with model
 25.451973 seconds (20.12 M allocations: 1.074 GiB, 1.86% gc time)
Set objective and constraint coefficients with direct model
Running HiGHS 1.8.1 (git hash: 4a7f24ac6): Copyright (c) 2024 HiGHS under MIT licence terms
 21.774826 seconds (20.18 M allocations: 465.435 MiB, 0.59% gc time, 0.21% compilation time)
Read constraint coefficients with model
  8.749680 seconds (1.46 M allocations: 15.767 GiB, 7.62% gc time, 0.06% compilation time)
Read constraint coefficients with direct model
156.650799 seconds (1.87 M allocations: 21.628 GiB, 0.76% gc time, 0.04% compilation time)

Do I do something wrong ?

Thank you in advance for any insight,

Best regards,

Nicolas.

module scjulia

using JuMP
using Gurobi

const GRB_ENV_REF = Ref{Gurobi.Env}()

function __init__()
    global GRB_ENV_REF
    GRB_ENV_REF[] = Gurobi.Env()
    return
end

function set_coefficient_model()
    create_optimizer() = Gurobi.Optimizer(GRB_ENV_REF[])
    model = Model(create_optimizer)

    @variable(model, x[1:10000])
    @constraint(model, constr[1:1000], 0 == 1)

    for i in eachindex(x)
        set_objective_coefficient(model, x[i], 1.0)
    end

    for i in eachindex(x), j in eachindex(constr)
        set_normalized_coefficient(constr[j], x[i], 1.0)
    end

    return model, x, constr
end

function set_coefficient_direct_model()
    model = direct_model(Gurobi.Optimizer(GRB_ENV_REF[]))

    @variable(model, x[1:10000])
    @constraint(model, constr[1:1000], 0 == 1)

    for i in eachindex(x)
        set_objective_coefficient(model, x[i], 1.0)
    end

    for i in eachindex(x), j in eachindex(constr)
        set_normalized_coefficient(constr[j], x[i], 1.0)
    end

    return model, x, constr
end

function read_coefficient_model(x, constr)
    @inbounds for i in 1:100, j in 1:100
        normalized_coefficient(constr[j], x[i])
    end
end

function read_coefficient_direct_model(x, constr)
    @inbounds for i in 1:100, j in 1:100
        normalized_coefficient(constr[j], x[i])
    end
end

function main()
    println("Set objective and constraint coefficients with model")
    @time model, x, constr = set_coefficient_model()
    println("Set objective and constraint coefficients with direct model")
    @time direct_model, direct_x, direct_constr = set_coefficient_direct_model()
    println("Read constraint coefficients with model")
    @time read_coefficient_model(x, constr)
    println("Read constraint coefficients with direct model")
    @time read_coefficient_direct_model(direct_x, direct_constr)
end

end # module scjulia

scjulia.jl (1.8 KB)

2

So my first question is why do you want to do this? What are you really trying to do?

Read coefficients

An improvement for all cases would be to query the constraint object once:

function read_coefficient(x, constr)
    for j in 1:100
        f_j = constraint_object(constr[j]).func
        for i in 1:100
            normalized_coefficient(f_j, x[i])
        end
    end
end

because the default implementation of normalized_coefficient is to query the full function and then extract a single number:

Gurobi

The Gurobi times look about what I expect. You’re setting 10_000 objective coefficients, and 10_000_000 constraint coefficients, and your constraint is fully dense!

The first set with Model that takes 25 sec seems slow. I’ll take a look to see if we can improve that.

HiGHS

Reading the constraint coefficients with direct model is a known issue: Highs_getRowsByRange is slow · Issue #207 · jump-dev/HiGHS.jl · GitHub

3

Hello,

Thank you for you reply.

Concerning the modification of the constraints, in a column generation approach instead of branching I enumerate all the missing variables and add them to the master. There can many new variables (up to 500 000 thousands) so it is not just a toy example on that aspect.

I agree with you that the 1s for the direct model is normal given the large number of coefficients that are modified. It is more the 25s for the standard models. In the actual algorithm, adding the new variables in the model (not direct) is much slower than the dynamic programming algorithm used to find the missing variable.

For the normalized_coefficient function, I guessed I was using it wrongly (I used it as I would use the attribute query function directly in gurobi in C/C++). I do that for a cutting plane algorithm where I am used to read directly the information in the model instead of keeping additional data structures.

Best regards,

Nicolas.

4

instead of keeping additional data structures

You should keep additional data structures, or query the constraint function once.

JuMP does to have O(1) access to the constraint coefficients.

5

Thanks for the tip. I’ll use that instead.

N.