Many apologies in advance if this topic has already been answered.
I am implementing an cutting plane algorithm for solving a class of large-scale LPs using JuMP and Gurobi. Because the model requires lots of RAM, I am trying to efficiently delete the (possibly large number of) non-binding constraints in each iteration of my algorithm. I am looking for guidance on the most efficient way to delete constraints.
Specifically, in the MWE below, I generate a linear program with a large number of constraints. After solving the LP, the code uses the delete function to remove the non-active constraints. (In my real code, I then add new constraints and resolve the problem.)
using JuMP
using Gurobi
println("Define random problem instance")
@time begin
m = 1000
n = 10
A = rand(m,n)
b = ones(m)
end
println("Define restricted optimization problem over active set")
@time begin
# For simplicity, suppose we have added all of the constraints.
active_set = Set()
for i=1:m
push!(active_set, i)
end
model = Model(Gurobi.Optimizer)
set_silent(model)
@variable(model, x[1:n] >= 0)
@constraint(model, cons[i=1:m; i in active_set], dot(A[i,:], x) ≥ b[i])
@objective(model, Min, sum(x[j] for j=1:n))
end
println("Solve restricted optimization problem")
@time optimize!(model)
println("Prepare to delete the non-active constraints")
@time begin
x_opt = value.(x)
to_remove = Vector{ConstraintRef}()
for i in active_set
if dot(A[i,:],x_opt) > b[i]
push!(to_remove, cons[i])
end
end
end
println("Delete the non-active constraints")
@time delete(model, to_remove)
println("Resolve the optimization problem")
@time optimize!(model)
The output of the above code is the following:
Define random problem instance
0.000918 seconds (4 allocations: 1.679 MiB)
Define restricted optimization problem over active set
Academic license - for non-commercial use only
0.598139 seconds (2.06 M allocations: 99.967 MiB, 29.81% gc time)
Solve restricted optimization problem
0.090948 seconds (140.88 k allocations: 20.427 MiB)
Prepare to delete the non-active constraints
0.018719 seconds (238.28 k allocations: 7.799 MiB)
Delete the non-active constraints
7.000508 seconds (237.78 k allocations: 6.809 MiB)
Resolve the optimization problem
0.000383 seconds (36 allocations: 1.094 KiB)
Clearly, the deletion step is the bottleneck in the code. I have done some searching through past pull requests and issues for JuMP related to deleting constraints (such as https://github.com/jump-dev/Gurobi.jl/pull/313 and the discussion here). However, I have not seemed to find a solution to this performance issue.
Is there any straightforward way to improve the performance of the above code? Specifically, are there any performance tips on efficiently deleting constraints in a JuMP model with the Gurobi solver? If not, is this possible with any other solvers? Any advice or guidance would be greatly appreciated!