[JuMP] Speeding up constraint violation inspection

Specific Domains Optimization (Mathematical)
1

Hello,

I’m trying to make an oracle that checks for constraint violations in a solved model (ie. constraints that were not initially in the model) and add some of them to the model to then reoptimize. The inspector looks like this:

function inspector(model, TAXA)
    τ = model[:τ]
    x = model[:x]
    triples = Dict{Int, NTuple{3,Int}}()
    for q in TAXA
        worst = 0
        for (i,j,p) in combinations(TAXA,3) 
            q ∉ (i,j,p) || continue
            violation = value(2(τ[i,j]+τ[j,q]+τ[p,q]) - τ[i,j] - τ[i,p] - τ[j,p] - (8 + 6*sum(x[q,v,2] for v in TAXA if v∉(i,j,p,q))))
            if violation < worst 
                worst = violation
                triples[q] = (i,j,p)
            end
        end
    end

TAXA is just a set used in the model. x and tau are variables (actually they are expressions that substitute underlying variables/sum of variables, for a clearer syntax).
This is a O(n^4) oracle that generate O(n) cuts, quite slow, but I find that adding all the constraints is faster than executing the above code so I believe I’m doing something inefficient here. Plus I’m getting the
Warning: The addition operator has been used on JuMP expressions a large number of times. This warning is safe to ignore but may indicate that model generation is slower than necessary. For performance reasons, you should not add expressions in a loop. Instead of x += y, use add_to_expression!(x,y) to modify x in place. If y is a single variable, you may also use add_to_expression!(x, coef, y) for x += coef*y.
I think the slow part is when I’m computing the violation for a quadruplet (i,j,p,q) but I don’t see where I’m doing what the Warning says I shouldn’t do, since I’m building the entire expression and evaluate it at once.

2

Your issue is building this expression. See Performance tips · JuMP

A simple fix might be:

function inspector(model, TAXA)
    τ = value.(model[:τ])
    x = value.(model[:x])
    triples = Dict{Int, NTuple{3,Int}}()
    for q in TAXA
        worst = 0
        for (i,j,p) in combinations(TAXA,3) 
            q ∉ (i,j,p) || continue
            violation = 2(τ[i,j]+τ[j,q]+τ[p,q]) - τ[i,j] - τ[i,p] - τ[j,p] - (8 + 6*sum(x[q,v,2] for v in TAXA if v∉(i,j,p,q)))
            if violation < worst 
                worst = violation
                triples[q] = (i,j,p)
            end
        end
    end

Now your for loop operate on Float64, not JuMP expressions.

1 Like