[gecode-users] Possible Bug - Increase IntVars Range and Gecode Stalls

[Christian Schulte]

Did you try it in Gist to see how large the search trees get or whether
Gecode just hangs?

 

After all, you exponentially increase the search space!

 

Christian

 

--

Christian Schulte, Professor of Computer Science, KTH,
www.ict.kth.se/~cschulte/

 

From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf
Of Navid Mohaghegh
Sent: Tuesday, January 14, 2014 5:04 PM
To: users at gecode.org
Subject: [gecode-users] Possible Bug - Increase IntVars Range and Gecode
Stalls
Importance: High

 

Hi Everyone,

 

My question:

I am wondering what is happening in below and why Gecode stalls stall whenI
increase the range of my IntegerVars (while its CPU utilization goes very
high) despite the fact that our constraints are not changed?

 

Background (http://navid.ca/gecode/test.cpp):

We are trying to solve a space. We can easily solve the space when our
variable ranges are small (e.g. 0 to 800). As soon as the range goes higher
(e.g. 0-1535) Gecode will stall and can not produce a solution for the space
with exactly the same constraints as before.

 

*	We have 4 groups of integer_array variables. They are called vars_a,
vars_b, vars_c and vars_d. And inside each of them, we have 15 integer
variables.

*	NavidTest(int n, int vars_a_max_, int vars_b_max_, int vars_c_max_,
int vars_d_max_, int vcost_max_); 
*	NavidTest* m = new NavidTest(15,  800, 500, 410, 60, 2000000000);
means:

*	n = 15
*	vars_a[0] ... vars_a[15] can have values from zero to vars_a_max_ =
800
*	vars_b[0] ... vars_b[15] can have values from zero to vars_b_max_ =
500
*	vars_c[0] ... vars_c[15] can have values from zero to vars_c_max_ =
410
*	vars_d[0] ... vars_d[15] can have values from zero to vars_d_max_ =
60
*	our cost variable can be have values from zero to vcost_max_ =
2,000,000,000

*	As we have quadratic cost functions and values can easily grow.

*	lift() method is where we add our constraints. 
*	For demonstration purpose, we have a method that once used, Gecode
can produce solution: it is called "void the_one_works()"

*	And we have another one (called: void the_one_doesnot_work) that can
not be solved using Gecode (it is perfectly solvable and we test our
solution in verify_answer() method)
*	The only difference between the_one_works() and
the_one_doesnot_work() is an increase in vars_a max range from 800 to 1535. 

 

 

 

I have found a mailing list entry stating a possible bug:

==========

From: victor.zverovich at ...
<http://gmane.org/get-address.php?address=victor.zverovich%2dRe5JQEeQqe8Avxt
iuMwx3w%40public.gmane.org>  <victor.zverovich at ...
<http://gmane.org/get-address.php?address=victor.zverovich%2dRe5JQEeQqe8Avxt
iuMwx3w%40public.gmane.org> >
Subject: bug in INT_VALUES_MAX
<http://news.gmane.org/find-root.php?message_id=CANawtxb3jmzB754b7zWaZMuG76T
7KJBwAj1PP%2bMmHgJL%3d0EKVQ%40mail.gmail.com> 
Newsgroups: gmane.comp.lib.gecode.user
<http://news.gmane.org/gmane.comp.lib.gecode.user> 
Date: 2013-06-21 22:20:18 GMT (29 weeks, 3 days, 17 hours and 17 minutes
ago)

There seems to be a trivial bug in INT_VALUES_MAX: SEL_VALUES_MIN is used
instead of SEL_VALUES_MAX. The attached patch fixes it.

Victor

==========

 

Can someone have a look and let me know?

*	We are using Gecode 4.2.1 on Linux
*	GCC 4.7.2 and also latest 4.9
*	Debian 64bit and CentOS 64bit  
*	My code and how I compile and run is here:
http://navid.ca/gecode/test.cpp

 

Thank you,

Navid

 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20140114/1ae21c00/attachment.html>