[gecode-users] Possible Bug - Increase IntVars Range and Gecode Stalls
Christian Schulte
cschulte at kth.se
Mon Jan 20 21:29:51 CET 2014
What does stall mean, again? Is it still searching (you can observe that in
Gist), that is making progress? Or is it dead.
To improve your model, check the perfect square example that comes with
Gecode and/or search for square packing on Helmut Simonis' webpage:
<http://4c.ucc.ie/~hsimonis/> http://4c.ucc.ie/~hsimonis/
Christian
--
Christian Schulte, www.ict.kth.se/~cschulte
From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf
Of Navid Mohaghegh
Sent: Thursday, January 16, 2014 09:23 PM
To: cschulte at kth.se; users at gecode.org
Subject: Re: [gecode-users] Possible Bug - Increase IntVars Range and Gecode
Stalls
Hi Christian,
Thank you for your reply.
I originally didn't use that as I didn't want to add another set of
variables for finishing corner of rectangles (Gecode nooverlap API has a
simple version that use fixed int width and int height).
Per your suggestion, I added two array variables for finishing corner that I
can employ the nooverlap API:
-defined integer array variables for starting point of rectangles (e.g. top
left corner): I called it vxs and vys (e.g. X0 and Y0 in Gecode MPG manual)
-defined integer array variables for width and height of rectangles: I
called it vw and vh (e.g. W and H in Gecode MPG manual)
-defined integer array variables for finishing point of rectangles (e.g.
lower right corner): I called it vxf and vyf (e.g. X1 and Y1 in Gecode MPG
manual)
-I removed all manual non-overllaping contraint that I manually added myself
and add the following:
//starting point width and hight will give us the finishing
point
for (i =0 ; i < this->n_vars; i++)
{
rel(*this, ( (vxs[i] + vw[i] == vxf[i]) && (vys[i] +
vh[i] == vyf[i]) ) );
}
//add nooverlap for all rectangles
nooverlap(*this, vxs,vw,vxf, vys,vh,vyf);
My code gets solved for lower ranges of X vars (e.g. vxs < 1000 and
vxf<1200) and the moment I change the x range to values greater than 1500
gecode stalls.
I appreciate your feedback.
Thank you,
Navid
On Jan 16, 2014, at 10:33 AM, Christian Schulte <cschulte at kth.se> wrote:
Hi,
Just very quick: did you look at the nooverlap constraint in Gecode?
Cheers
Christian
--
Christian Schulte, Professor of Computer Science, KTH,
<http://www.ict.kth.se/~cschulte/> www.ict.kth.se/~cschulte/
From: Navid Mohaghegh [ <mailto:navid at navid.ca> mailto:navid at navid.ca]
Sent: Thursday, January 16, 2014 3:32 PM
To: <mailto:users at gecode.org> users at gecode.org
Cc: <mailto:cschulte at kth.se> cschulte at kth.se
Subject: Re: [gecode-users] Possible Bug - Increase IntVars Range and Gecode
Stalls
Hi everyone,
I tried Gist as Christian mentioned. Gist will not terminate for higher
ranges (attached screenshot shows that I had to stop Gist manually for range
1535).
Could you please point me in the right direction about what I have to more
efficient for this problem:
-Like bin-packing problem, we have bunch of rectangles that shouldn't
overlap with each other.
-Unlike bin-packing, the width and hight of the rectangles can be variable
(e.g. if we have more space in our sheet, we don't mind a rectangle gets
bigger).
-We have bunch of constraint for the size and location of rectangles.
-In below, 15 rectangles, 4 array of variables (2 arrays for X,Y location
and 2 variables for Width,Height which is for size)
Could you please let me know?
Thank you,
Navid
<image001.png>
On Jan 14, 2014, at 11:42 AM, Christian Schulte < <mailto:cschulte at kth.se>
cschulte at kth.se> wrote:
The bug you refer to has been fixed. But try Gist, there you can see what
happens.
Cheers
Christian
--
Christian Schulte, Professor of Computer Science, KTH,
<http://www.ict.kth.se/~cschulte/> www.ict.kth.se/~cschulte/
From: <mailto:users-bounces at gecode.org> users-bounces at gecode.org [
<mailto:users-bounces at gecode.org> mailto:users-bounces at gecode.org] On Behalf
Of Navid Mohaghegh
Sent: Tuesday, January 14, 2014 5:39 PM
To: <mailto:cschulte at kth.se> cschulte at kth.se
Cc: <mailto:users at gecode.org> users at gecode.org
Subject: Re: [gecode-users] Possible Bug - Increase IntVars Range and Gecode
Stalls
Hi Christian,
Thank your for your reply. I didn't try Gist yet, I will go and look at
sample code to learn Gist and I will give it a shot.
Could you kindly have a look at this comment in mailing list: "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."
I am asking this as mu space get solved by Gecode almost instantly (less
than 1ms on a 128 GB ram, quad CPU, 64 cores workstation) for values like
1199. And the moment it goes to 1200 it will stalls. After all it should get
slow (I agree with you), but not stall/freeze for 5 days. That is the main
reason I suspect a tiny bug somewhere.
I will also look at Gist as well as you instructed.
Thank you,
Navid
On Jan 14, 2014, at 11:18 AM, Christian Schulte < <mailto:cschulte at kth.se>
cschulte at kth.se> wrote:
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,
<http://www.ict.kth.se/~cschulte/> www.ict.kth.se/~cschulte/
From: <mailto:users-bounces at gecode.org> users-bounces at gecode.org [
<mailto: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: <mailto:users at gecode.org> 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>
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:
<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> victor.zverovich at ...>
Subject:
<http://news.gmane.org/find-root.php?message_id=CANawtxb3jmzB754b7zWaZMuG76T
7KJBwAj1PP%2bMmHgJL%3d0EKVQ%40mail.gmail.com> bug in INT_VALUES_MAX
Newsgroups: <http://news.gmane.org/gmane.comp.lib.gecode.user>
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> http://navid.ca/gecode/test.cpp
Thank you,
Navid
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20140120/1899da05/attachment-0001.html>
More information about the users
mailing list