[gecode-users] Limits on nonlinear constraints

[Javier Romero]

Hi,
I'm a newbie in Gecode, but in the first stages of trying it i've found
something that puzzles me. After writing a program with a set of highly
nonlinear constraints which includes the following constraint (apart from
others)

    IntVar k = expr(*this, 2*x0*x1*x2);
    IntVar kc01= (*this,x2*(sqr(x0)+sqr(x1)-sqr(d01min)));
    IntVar kc02= (*this,x1*(sqr(x0)+sqr(x2)-sqr(d02min)));
    IntVar kc12= (*this,x0*(sqr(x2)+sqr(x1)-sqr(d12min)));
    rel(*this,k*(sqr(kc01)+sqr(kc02)+sqr(kc12)) < (k*k*k+2*kc01*kc02*kc12));

 i get an output like this:

Initial
        propagators: 0
        branchers:   0

Summary
        runtime:      0.000 (0.174000 ms)
        solutions:    0
        propagations: 0
        nodes:        0
        failures:     1
        peak depth:   0
        peak memory:  18 KB
That is, it returns inmediately with no solution. However, the problem has a
solution, and actually it finds it by commenting the last lined of the code
posted above (by chance; the constraint is actually necessary). This is how
the output looks when the solution is found:
Initial
        propagators: 82
        branchers:   1

Summary
        runtime:      54.402 (54402.259000 ms)
        solutions:    1
        propagations: 638013328
        nodes:        1237660
        failures:     618828
        peak depth:   414
        peak memory:  122 KB

I tested manually (and with a python script) that the solution obtained is
compliant with the constraint that was removed. So i wonder if there is a
limitation on the level of the nonlinearities in Gecode (i think it's
unlikely), in the number of constraints (also unlikely) or what else could
have happened. The code is basically an adaptation of SMM example to my
arithmetic constraints. I can post it if necessary.

Best regards,
-- Javier Romero --
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20100820/e0f691b7/attachment.htm>