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 <[email protected]> wrote:
> Hi,
>
> Just very quick: did you look at the nooverlap constraint in Gecode?
>
> Cheers
> Christian
>
> --
> Christian Schulte, Professor of Computer Science, KTH,
> www.ict.kth.se/~cschulte/
>
> From: Navid Mohaghegh [mailto:[email protected]]
> Sent: Thursday, January 16, 2014 3:32 PM
> To: [email protected]
> Cc: [email protected]
> 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 <[email protected]> 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,
> www.ict.kth.se/~cschulte/
>
> From: [email protected] [mailto:[email protected]] On Behalf Of
> Navid Mohaghegh
> Sent: Tuesday, January 14, 2014 5:39 PM
> To: [email protected]
> Cc: [email protected]
> 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 <[email protected]> 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,
> www.ict.kth.se/~cschulte/
>
> From: [email protected] [mailto:[email protected]] On Behalf Of
> Navid Mohaghegh
> Sent: Tuesday, January 14, 2014 5:04 PM
> To: [email protected]
> 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@... <victor.zverovich@...>
> Subject: bug in INT_VALUES_MAX
> Newsgroups: 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
>
_______________________________________________
Gecode users mailing list
[email protected]
https://www.gecode.org/mailman/listinfo/gecode-users
