Numerical constraints (expressions over reals) with repetitions of variables and solving polynomials

[gadavidd]

Solving a polynomial problem with reals in choco-solver using propagation, I obtained an unexpected domain interval that occurs when variables are repeated in the expression. Something close to values within the domain that lead to a contradiction (false positive or no-good), for example, consider the following expression I:

I) 100 = b*(b+c):

For c = 0, the domain of b will be reduced to the interval between 8.73475 and 10.28125;
For c = 1, the domain of b will be reduced to the interval between 8.7254 and 10.272272.

Model model;
model = new Model("Test");
RealVar a = model.realVar("b", 0, 100, 0.000001);
RealVar b = model.realVar("b", 0, 100, 0.000001);
RealVar c = model.realVar("c", 0, 100, 0.000001);

a.eq(100.0).post();
c.eq(1.0).post();
a.eq(b.mul(b.add(c))).post();

Solver solver = model.getSolver();
solver.propagate();
System.out.printf("[%s %s %s]\n", a, b, c);

In both cases, the domain of b should be in the range of 9.94987 and 10. Third-degree equations still present a difficulty, even if they are well-behaved real roots. For example, consider the following expression II:

II) x³-10x² + 31x - 30 = 0

Example II has real roots 2, 3 and 5 and the range of the domain of x will return the domain between 0.8244 and 9.461895 after propagation.

Although the Solver (solution search) manages to find the expected solution for both scenarios, but in configuration tasks the realize result of the propagation a little inconvenient scenarios may have the emergence of false positives seem to be present during propagation, such as the values 10.28125 for expression I and 9 for expression II. This seems to me to be a behavior unique to the propagation. of multiple variables that is repeated through PropEquation, if the power operation is performed, a filtering of domains closer to the correct one should occur.

I believe it is related to the discussions of HC4 and the Mohc algorithm in [1].

[1] ARAYA, Ignacio; TROMBETTONI, Gilles; NEVEU, Bertrand. Exploiting monotonicity in interval constraint propagation. In: Proceedings of the AAAI Conference on Artificial Intelligence. 2010. p. 9-14.