# Jump delete is slower than building a new model

I have a rather large JuMP model which takes >0.2 seconds to build but only 0.1 seconds to solve. I have to solve this model thousands of times with only a small change to a portion of the constraints, it therefore seems like a good use for `delete`. However, I’m finding delete is slower than building a new model, see a minimum working example below

``````using JuMP
using HiGHS
x_min =rand(100,100)

@time begin
m = Model(HiGHS.Optimizer)

@variable(m, x[1:100,1:100])

@constraint(m, x_min_con, x .>= x_min)

@objective(m, Min, sum(x))
nothing
end # 0.032046 seconds (316.76 k allocations: 21.476 MiB, 55.44% compilation time)
optimize!(m)

@time delete(m, vec(x_min_con)) # 1.134940 seconds (95.95 k allocations: 1.360 GiB, 7.62% gc time)
# need to rebuild the model
@time delete.(m, x_min_con) # 1.145643 seconds (105.96 k allocations: 1.360 GiB, 7.59% gc time)
``````

If you don’t use and optimiser the deletion times are similar to the model times, I’ve tried using both Gurobi and HiGHS which both cause the far larger deletion times.

Am I using delete wrong here? Or is it possible that rebuilding the model can be orders of magnitude faster than deleting?

What part of the constraints are you changing? There might be a better way than deleting.

In general, deleting a constraint is an expensive operation, because we need to modify the constraint matrix, and update the mapping between JuMP constraints and the row inside the solver.

We should be able to improve things somewhat though, because this is a clear bottleneck in JuMP, not HiGHS:

``````using JuMP
using HiGHS

x_min = rand(100,100)

@time begin
m = Model(HiGHS.Optimizer)
@variable(m, x[1:100, 1:100])
@constraint(m, x_min_con, x .>= x_min)
@objective(m, Min, sum(x))
m
end
optimize!(m)

using ProfileView
ProfileView.@profview delete.(m, x_min_con)
``````

The widest part is all about deleting elements from an ordered dictionary which maps constraint indices to their row in the solver.

1 Like

I have a new method here that should improve things: Fix performance of deleting multiple linear constraints by odow · Pull Request #144 · jump-dev/HiGHS.jl · GitHub

``````julia> using JuMP

julia> using HiGHS

julia> function main(flag)
x_min = rand(100,100)
m = direct_model(HiGHS.Optimizer())
set_silent(m)
@variable(m, x[1:100, 1:100])
@constraint(m, x_min_con, x .>= x_min)
@objective(m, Min, sum(x))
optimize!(m)
# y = vec(x_min_con)
if flag
@time delete(m, vec(x_min_con))
else
@time delete.(m, x_min_con)
end
return m
end
main (generic function with 2 methods)

julia> main(true);
0.001193 seconds (42 allocations: 819.688 KiB)

julia> main(false);
2.216103 seconds (65.94 k allocations: 1.359 GiB, 9.87% gc time)

julia> main(true);
0.001752 seconds (42 allocations: 819.688 KiB)

julia> main(false);
2.234672 seconds (65.94 k allocations: 1.359 GiB, 10.08% gc time)
``````
2 Likes

These figures are far better.

Despite this it seems you have achieved the improvements by a PR in HiGHS.jl, so I presume that the same issue will be present in Gurobi?

``````julia> using JuMP
julia> using Gurobi
julia> function main(flag)
x_min = rand(100,100)
m = Model(Gurobi.Optimizer) # not a direct model
set_silent(m)
@variable(m, x[1:100, 1:100])
@constraint(m, x_min_con, x .>= x_min)
@objective(m, Min, sum(x))
optimize!(m)
# y = vec(x_min_con)
if flag
@time delete(m, vec(x_min_con))
else
@time delete.(m, x_min_con)
end
return m
end
main (generic function with 1 method)

julia> main(true);
0.787790 seconds (40.03 k allocations: 1.865 MiB)

julia> main(false);
0.795973 seconds (50.04 k allocations: 1.866 MiB)

julia> main(true);
0.798421 seconds (40.03 k allocations: 1.865 MiB)

julia> main(false);
0.795956 seconds (50.04 k allocations: 1.866 MiB)
``````

Is it possible to also improve this for Gurobi using a similar method?

Despite this it seems you have achieved the improvements by a PR in HiGHS.jl, so I presume that the same issue will be present in Gurobi?

To clarify, I meant it was a problem in the Julia side of things, not in the upstream C++ solver `ERGO-Code/HiGHS`. So yes, this will also need a similar fix in Gurobi.jl.

1 Like

Ah. Gurobi has the method. The problem is the bridges:

``````julia> using JuMP

julia> import HiGHS

julia> import Gurobi

julia> function main(optimizer, flag; bridges)
x_min = rand(100,100)
m = Model(optimizer; add_bridges = bridges)
set_silent(m)
@variable(m, x[1:100, 1:100])
@constraint(m, x_min_con, x .>= x_min)
@objective(m, Min, sum(x))
optimize!(m)
if flag
@time delete(m, vec(x_min_con))
else
@time delete.(m, x_min_con)
end
return
end
main (generic function with 1 method)

julia> main(Gurobi.Optimizer, true; bridges = true)
1.274187 seconds (138.19 k allocations: 3.311 MiB)

julia> main(Gurobi.Optimizer, false; bridges = true)
1.313978 seconds (148.71 k allocations: 3.319 MiB)

julia> main(HiGHS.Optimizer, true; bridges = true)
2.356010 seconds (175.15 k allocations: 1.362 GiB, 9.78% gc time)

julia> main(HiGHS.Optimizer, false; bridges = true)
2.349330 seconds (204.64 k allocations: 1.362 GiB, 9.51% gc time)

julia> main(Gurobi.Optimizer, true; bridges = false)
0.011561 seconds (138.71 k allocations: 3.433 MiB)

julia> main(Gurobi.Optimizer, false; bridges = false)
1.280514 seconds (148.71 k allocations: 3.319 MiB)

julia> main(HiGHS.Optimizer, true; bridges = false)
0.010352 seconds (119.25 k allocations: 3.745 MiB)

julia> main(HiGHS.Optimizer, false; bridges = false)
2.384257 seconds (204.64 k allocations: 1.362 GiB, 9.59% gc time)
``````
1 Like

This will be fixed in the next release of MathOptInterface: [Bridges] fix deletion of a vector of constraints by odow · Pull Request #2072 · jump-dev/MathOptInterface.jl · GitHub

``````julia> using JuMP

julia> import HiGHS

julia> import Gurobi

julia> function main(optimizer, flag; bridges)
x_min = rand(100,100)
m = Model(optimizer; add_bridges = bridges)
set_silent(m)
@variable(m, x[1:100, 1:100])
@constraint(m, x_min_con, x .>= x_min)
@objective(m, Min, sum(x))
optimize!(m)
if flag
@time delete(m, vec(x_min_con))
else
@time delete.(m, x_min_con)
end
return
end
main (generic function with 1 method)

julia> main(Gurobi.Optimizer, true; bridges = true)
0.012051 seconds (157.68 k allocations: 3.723 MiB)

julia> main(Gurobi.Optimizer, false; bridges = true)
1.347333 seconds (148.70 k allocations: 3.319 MiB)

julia> main(HiGHS.Optimizer, true; bridges = true)
0.009889 seconds (119.25 k allocations: 3.745 MiB)

julia> main(HiGHS.Optimizer, false; bridges = true)
2.359132 seconds (204.63 k allocations: 1.362 GiB, 9.89% gc time)

julia> main(Gurobi.Optimizer, true; bridges = false)
0.011513 seconds (138.70 k allocations: 3.433 MiB)

julia> main(Gurobi.Optimizer, false; bridges = false)
1.334790 seconds (148.70 k allocations: 3.319 MiB)

julia> main(HiGHS.Optimizer, true; bridges = false)
0.010266 seconds (119.25 k allocations: 3.745 MiB)

julia> main(HiGHS.Optimizer, false; bridges = false)
2.403712 seconds (204.63 k allocations: 1.362 GiB, 9.84% gc time)
``````
1 Like