[gecode-users] Limits on nonlinear constraints

[Guido Tack]

Javier Romero wrote:

> 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:
[...]
> 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:
[...]
> 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.

If you could give me a small example that I can compile and run, I can have a look.  The code for posting non-linear expressions is relatively new, and there may be bugs that our test suite has not found.

One thing you could try is to decompose the constraints (in particular the last line) manually, i.e. not use anything from minimodel.hh, but declare temporary IntVars and then only use the mult, linear, and sqr functions from int.hh.  If that works, then it's definitely a problem in how minimodel decomposes the constraint.

Cheers,
	Guido

-- 
Guido Tack, http://people.cs.kuleuven.be/~guido.tack/