Efficient deletion of affine constraints

Specific Domains Optimization (Mathematical)
,
1

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!

2

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.

3

Works perfectly! Many thanks!

4

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