[Nonlinear] detect common subexpressions

[odow]

There is tooling in MOI.Nonlinear.ReverseAD to exploit common subexpressions, but we don't actively exploit this when parsing ScalarNonlinearFunction.

I wonder if we could walk the tape somehow to detect and reduce common subexpressions that are at least N nodes long.

It would help: https://github.com/jump-dev/JuMP.jl/issues/3729#issuecomment-2060549713

[odow]

Some possible options:

1. Create a single unified expression graph (as opposed to the current expression tree). Change quite a lot of how ReverseAD processes functions etc.
2. Don't do anything. Add a new decision variable with y = f(x) for expressions. This makes things very explicit.
3. Add something new type/index to JuMP/MOI. But we're breaking the abstraction quite a bit.
4. Add a univariate :subexpression operator to MOI. So: @expression(model, expr, subexpression(sin(x) + 1)). Solvers would see this during parsing, and could choose to ignore, or store it in a common expression.

I don't have a strong opinion yet. But our current approach requires us to smack the modeler on the hand and tell them they're holding it wrong and that they should do (2): https://github.com/jump-dev/JuMP.jl/issues/3729#issuecomment-2060586587

[odow]

Another example is https://github.com/jump-dev/MathOptInterface.jl/issues/2496

[Downsite]

I can't comment on the effect on AD. However, if this also would concern the form in which problem is given to (global) solvers, I have some thoughts:

• doing (2) might have impact on global solvers. Many global solvers based on factorable functions may do that themselves, but some solvers do not. These sometimes have a huge benefit from not having to branch on the "intermediate" factors ("reduced space formulation"). This is admittedly a corner case, so maybe other merits of option 2 outweigh this.
• maybe there is already very efficient methods for doing (1) in Julia. My experience with using DAGs to eliminate common subexpressions is that one can very easily create situations where parsing larger problems becomes very expensive. Maybe this is something to keep in mind.
• (4), seems neat, although I do not quite get the difference between that and defining @NLexpression as discussed in #3738.

[odow]

doing (2) might have

I was imagining that we would ask the user to do this, not JuMP or MathOptIntnerface.

My experience with using DAGs to eliminate common subexpressions is that one can very easily create situations where parsing larger problems becomes very expensive.

Yes, this is one reason why we don't do this at the JuMP level. We very explicitly choose to do the simplest possible thing, even if it means that it isn't the best thing to do inn a bunch of cases.

(4), seems neat, although I do not quite get the difference

Yeah, to be decided. It's really just a syntax decision of how to communicate potential subexpressions to the solver.

[odow]

Closing in favor of https://github.com/jump-dev/JuMP.jl/issues/3738. No need to duplicate our discussions.