Potential hash collision for nonlinear subexpressions

[basberr]

Hi,

Thanks for your work and release. As my problems of interest have plenty of common subexpressions, I tried v1.31 to check for any speed improvement (for build time so far if I understood correctly).

However, that release broke my code (which worked with v1.30.1).
The bug is silent and JuMP just seems to build a different optimization problem.

Here is a MWE (with the help of Claude).

using JuMP

n = 25_000 # 5_000 seems to be OK for both versions

model = Model()
@variable(model, x)
cons = [@constraint(model, sin(x) * i <= 0) for i in 1:n]

# The stored function is  -( *(sin(x), i), 0.0 ) ; recover that i.
function multiplier(model, c)
    f = MOI.get(JuMP.backend(model), MOI.ConstraintFunction(), JuMP.index(c))

    got = nothing
    walk(g) =
        if g isa MOI.ScalarNonlinearFunction
            g.head === :* && for a in g.args
                a isa Real && (got = a)
            end
            foreach(walk, g.args)
        end
    walk(f)
    return got
end

bad = [(i, m) for (i, c) in enumerate(cons) for m in (multiplier(model, c),) if m != i]

println("JuMP ", pkgversion(JuMP))
println("wrong constraints: ", length(bad), " / ", n)
for (i, got) in first(bad, 5)
    println("  constraint $i stored as sin(x) * $got")
end

Outputs:

JuMP 1.31.0
wrong constraints: 141 / 25000
constraint 14989 stored as sin(x) * 10611.0
constraint 15001 stored as sin(x) * 10600.0
constraint 15029 stored as sin(x) * 10567.0
constraint 15263 stored as sin(x) * 10292.0
constraint 15280 stored as sin(x) * 10270.0

JuMP 1.30.1
wrong constraints: 0 / 25000

[AayushSabharwal]

XRef SciML/ModelingToolkit.jl#4810 The objectid-based cache added in #4032 is likely invalid. As mentioned in the ModelingToolkit issue, Julia will reuse objectid values if the object is garbage collected. Here, the problem is that objectid(f) is used as a key in

JuMP.jl/src/jump_moi_function.jl

Lines 170 to 173 in f954751

	key = objectid(f)
	if haskey(model.subexpressions, key)
	return model.subexpressions[key]
	end

. f is later garbage collected, and another expression gets the same objectid by coincidence. This then causes a false cache hit. A solution may be to use Base.IdDict instead of Dict{UInt, ..}. Note that this will keep all the f expressions alive until the cache is cleared. The issue in ModelingToolkit also has a reproducer which allows observing the objectid collisions.

[odow]

Looking at this now.

[odow]

Cache invalidation is hard.

[odow]

I'm going to temporarily revert it #4205 and issue a patch release. We can take a little longer to discuss what the right approach is in #4204.

[AayushSabharwal]

Thank you for the prompt response!