[BUG] OutOfMemoryError in choco-solver 4.10.7 or lastest

[gadavidd]

Describe the bug
After updating the choco-solver for version 4.10.7 or latest my programs won't work. In 4.10.6 or the oldest, it works well.

In plenty of other scenarios used by my application, the library behavior remains almost the same as seen in older versions, but in this specific use case where I calculate a power using variables with large domains, the memory usage rapidly increases, and the application crashes.

To Reproduce
I noticed that the program stops in the class PropCompactTable in method computeSupports(Tuples tuples) when posting the constraint in the following code:

package org.example;
import org.chocosolver.solver.Model;
import org.chocosolver.solver.Solution;
import org.chocosolver.solver.variables.IntVar;

public class App
{
    public static void main(String[] args) {

        Model model = new Model();
        IntVar xvar = model.intVar("xvar",-10000,10000,true);
        IntVar yvar = model.intVar("yvar",-10000,10000,true);

        yvar.eq(xvar.pow(2)).post();

        Solution solution = model.getSolver().findSolution();
    }
}

Expected behavior
In choco-solver 4.10.6, when calculating with pow under the same conditions, the program does not go through this method and if the domain limit is exceeded there is an exception handling:
pow_exp_1: consider reducing the bounds to avoid unexpected results
Is this a bug in the latest versions?

Error log
In choco-solver 4.10.10 the log's error is:

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
    at org.chocosolver.solver.constraints.extension.nary.PropCompactTable.computeSupports(PropCompactTable.java:102)
    at org.chocosolver.solver.constraints.extension.nary.PropCompactTable.<init>(PropCompactTable.java:61)
    at org.chocosolver.solver.constraints.IIntConstraintFactory.table(IIntConstraintFactory.java:451)
    at org.chocosolver.solver.constraints.IIntConstraintFactory.table(IIntConstraintFactory.java:426)
    at org.chocosolver.solver.constraints.IIntConstraintFactory.table(IIntConstraintFactory.java:2423)
    at org.chocosolver.solver.constraints.IIntConstraintFactory.table(IIntConstraintFactory.java:2383)
    at org.chocosolver.solver.expression.discrete.arithmetic.UnCArExpression.intVar(UnCArExpression.java:125)
    at org.chocosolver.solver.expression.discrete.relational.BiReExpression.fill(BiReExpression.java:201)
    at org.chocosolver.solver.expression.discrete.relational.BiReExpression.decompose(BiReExpression.java:149)
    at org.chocosolver.solver.expression.discrete.relational.ReExpression.post(ReExpression.java:138)
    at org.example.App.main(App.java:14)

Environment (please complete the following information):

• Choco-solver version: 4.10.7 and latest
• JRE : 11,17 and 19

[cprudhom]

Hi

The problem was already there in 4.10.6 but we allow bigger domain for integer variable in the last versions of choco.
So, now the problem is visible...
I think this is related to #978.

I cannot see immediate patch, right now.
The thing is: an intermediate variable is introduced by the expression constructor to store the result of xvar.pow(2).
Its domain is defined as [0,100_000_000] since it does detect that it should be reduced to [0,10000] because of the second part of the expression yvar.eq(...).

Presumably an expression analyser should be developed (a fist step could be #983) to tighten intermediate variables' domain.

[jgFages]

Hi,

Do we have a direct implementation of the pow constraint (i.e. not relying on table reformulation) ?

[cprudhom]

Indeed, that could be a patch but I don't have it on hand.

[cprudhom]

Well, if n == 2 which is the case here, we have PropSquare. I can fix the issue for this case (only).
But I suppose that all cases where n is an integer can be derived from this propagator.

[jgFages]

I guess n=2 in 80% of the cases so yes it would be good to have it !