Efficient deletion of affine constraints

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)

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)

    model = Model(Gurobi.Optimizer)
    @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))

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

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!

Try this with

model = direct_model(Gurobi.Optimizer())

Gurobi has some very peculiar semantics around how it updates the model after a deletion, so it can be hard to make it efficient in all cases.

Works perfectly! Many thanks!

Great! It’s on our radar to fix the first case. But it requires some extra plumbing in various places.