Infinite recursion in DepthFirstSearch about jacop HOT 4 CLOSED

Hi,

We have not seen this problem for a long time.

I assume you have changed stack size with the help of -Xss flag for JVM, right? Sometimes, when people have very large number of variables we were seeing this problem and increasing the size of stack was helping in preventing StackOverflow problem.

If -Xss switch does not help in your case then we need to be able to replicate your problem on our machine to be able to figure out the source of the problem.

There were sometimes situation, when for example user configuration of DepthFirstSearch that was not properly providing the choice selection for the search was causing the infinite search depth as each choice was not properly restricting the search space.

best,
Radek

from jacop.

Thanks for getting back to me.

I have not modified the JVM's stack size from the default, and I'm not using a large number of variables (an example with 10 variables and 7 constraints causes the issue).

I have extracted an example CSP that causes the problem into nevik/jacop-recursion-bugtest. It's a Java Maven project that only has JaCoP 4.3 as a dependency and its only Java file creates the CSP situation causing the problem.

A few notes on this:

• The CSP is originally generated by a program from a different representation;
• That causes the weird-looking long variable names;
• and it also causes the redundant/duplicate constraints;
• the "enumerated" integer domains are created as such because that's how it is in the generated code, I've not tested whether this has an effect on the bug (that the so-created domains are contiguous is a special case of this example);
• I'm aware this CSP is very much underconstrained -- however, if this is a problem for JaCoP, I'd like to have a way to find out or get an appropriate exception from JaCoP instead of a JVM-crashing error.

Thanks again and please let me know if this reproduces the problem for you, and if you find any problems with it.

from jacop.

Hi,

Thanks for the program. I was able to replicate your problem.

First, please note that, if you change the domains of the variables from very large number of 2147483647 into 21, and 2147483647 into -21 then you find a solution quickly without a problem.

You are violating the min and maximum value of the int var domain in JaCoP. We should enforce it a bit more rigorously and fail at model creation phase. If you use the following values -50000000 and 50000000 for min and max value of your int vars then again JaCoP is able to find a solution. Those values are currently being used by JaCoP for min and max value allowed in the domain of int var.

Thanks for the report. We will need to add more safety checks to force respecting the min and max values. When those bounds are respected then the search will not exibit the exception you have.

You want to be careful with specifying unnecessary large domains, sometimes depending on the search you choose it may be very detrimental to the search efficiency.

Hope that helps.

best,
Radek

from jacop.

Ahh, that does make sense.

I was previously not careful enough about that, because the problem from which I generate this CSP is not specified entirely over FDVs -- instead, some of the integer variables have base domains that have open (infinite) lower and/or upper bounds (that's what causes Integer.MAX_VALUE to appear, for example).

I did run into a similar issue when instantiating XplusYeqZ constraints, which run overflow checks on the variable domains.

I'm looking forward to seeing more checks for this in JaCoP (even if only as assertions), but this was definitely my fault for discounting JaCoP's expectation of finite domains.

Thanks for your help!

from jacop.