JuMP 0.21: how to efficiently delete non-binding constraints in an LP?

Specific Domains Optimization (Mathematical)
1

Dear folks,

I like to delete non-binding constraints in an LP, i.e., constraints with zero shadow price, and then re-optimize. I tried:

optimize!( model )
if has_duals( model )
    num_cons = num_constraints(model, GenericAffExpr{Float64,VariableRef}, MOI.LessThan{Float64})
    less_than_constraints = all_constraints(model, GenericAffExpr{Float64,VariableRef}, MOI.LessThan{Float64})

    for i in num_cons:-1:1
        if shadow_price(less_than_constraints[i]) == 0
            delete(model, less_than_constraints[i])
        end
    end
end
optimize!( model )

However, after the first constraint is removed the following error is thrown:

ErrorException("The shadow price is not available because no dual result is available.")

What works is pushing the constraints to delete in a vector, and then deleting them all at once:

if has_duals( model )
    num_cons = num_constraints(model, GenericAffExpr{Float64,VariableRef}, MOI.LessThan{Float64})
    less_than_constraints = all_constraints(model, GenericAffExpr{Float64,VariableRef}, MOI.LessThan{Float64})
    non_binding_cons = Any[]

    for i in num_cons:-1:1
        if shadow_price(less_than_constraints[i]) == 0
            push!( non_binding_cons, less_than_constraints[i] )
        end
    end
    delete(model, non_binding_cons)
end

The latter approach, however, does not seem very efficient to me. Do you have any better ideas?

Thanks in advance.

2

I do not see any way to make this more efficient from your side. What is the solver you are using ? Can you try to use direct_model instead of Model? If it solves the performance issue then, the issue should be resolved by Fast deletion of vector of constraints for Utilities.AbstractModel · Issue #1102 · jump-dev/MathOptInterface.jl · GitHub

2 Likes
3

I use CPLEX, and tried to switch to a direct_model which seems to work so far. The behavior is, however, the same as outlined in my original post. Unfortunately, I do not really understand how to resolve that issue with the link you have shared.

4

I do not really understand how to resolve that issue with the link you have shared.

What I meant by this is that once this issue is resolved and an new version of MathOptInterface is released, the deletion of a vector of constraints will be much improved. With direct_model, you don’t use any cache so you won’t see the difference but with Model, you also need to delete from the cache.

The behavior is, however, the same as outlined in my original post.

We have also no specialized implementation for deleting vector of constraints in CPLEX.jl. One was added recently for Gurobi.jl: Adds a specialization of MOI.delete that deletes a batch of constraints. by henriquebecker91 · Pull Request #313 · jump-dev/Gurobi.jl · GitHub. We probably need to do something similar.

2 Likes
5

The first error you get (when deleting constraints one by one), is because the solution is thrown away when the problem is modified. Thus, you should query the entire dual vector first, then delete constraints.

In any case, expect the deletion of constraints to be slow.
That is partly because JuMP/MOI needs to ensure existing indices remain valid, and that takes a bit of time. If constraints are deleted one by one, it even takes a lot of time.

3 Likes
6

I am busy writing a paper now, so I cannot extend the constraint deletion for CPLEX.jl right now (want to do it someday). But if there is interest I can give some guidance. In Gurobi.jl the performance issues were a little more terrible, so I focused on it.

However, I think the problem here was that @mike_k thought that creating a vector of dual values was inefficient, maybe because this clearly allocates. But I would say that is the best solution, I would do it even if the problem of the dual values being cleaned after the first deletion did not exist; because this way, when a specialization for batch delete of constraints in CPLEX.jl is made available, the code will be automatically the most efficient possible. Just use broadcast instead of that loop like: less_than_constraints[shadow_price.(less_than_constraints) .== 0];

1 Like