[gecode-users] Counting clones

[Marco Correia]

I see. So the runtime gain due to setting c_d>1 with DFS should only 
come from the set of clones avoided along the rightmost path (i.e. the 
path from the search tree root to the solution). I'm thinking that all 
the subtrees to the left of the rightmost path were fully explored and 
therefore setting c_d>1 there should not provide any speedup there.  Is 
this correct?

Thanks
Marco
> Guido Tack <mailto:tack at gecode.org>
> June 2, 2012 3:00 AM
> On 02/06/2012, at 5:03 AM, Marco Correia wrote:
>
> You may in fact save runtime in case you don't explore the entire 
> tree.  E.g. when you're only searching for one solution (not 
> optimising), many branches may remain unexplored.  With a higher c_d, 
> you will have fewer clones than choice points, and in some cases (deep 
> trees) search will also be faster.
>
> Cheers,
> Guido
>
> -- 
> Guido Tack
> http://www.csse.monash.edu/~guidot/ 
> <http://www.csse.monash.edu/%7Eguidot/>
>
>
> Marco Correia <mailto:marco.v.correia at gmail.com>
> June 1, 2012 8:03 PM
> Hi Christian,
>
> Thanks for the reply, I think I got it. I was under the impression 
> that recomputation (and adaptive recomputation) where techniques for 
> optimizing runtime performance when compared with standard copy since 
> recomputing could perhaps be faster than copying for some cases. But 
> now I see I was wrong and that their purpose is only to save space. 
> This means that setting c_d=1  should always provide faster runtime 
> than any other method (assuming that the problem at hand does not 
> require huge amounts of memory). Am I getting the right picture now, 
> or am I oversimplifying?
>
> Thanks!
> Marco
> Christian Schulte <mailto:cschulte at kth.se>
> June 1, 2012 7:41 PM
> Hi Marco,
>
> Well, the number of clones _is_ the same for any value of c-d or a-d! You
> have to backtrack, so you have to make a clone! The difference is that you
> clone different spaces.
>
> Christian
>
> --
> Christian Schulte, www.ict.kth.se/~cschulte/
>
>> -----Original Message-----
>> From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On
>> Behalf Of Marco Correia
>> Sent: Friday, June 01, 2012 6:54 PM
>> To: 'gecode list'
>> Subject: [gecode-users] Counting clones
>>
>> Hi,
>>
>> I suspect the answer to the following question should be somewhere in the
> MPG
>> document, but I was unable to find it - apologies if this is the case.
>>
>> I am interested on obtaining the number of clones for a specific example
> when
>> subject to different value for the c_d parameter in the context of a DFS
> search. I
>> believe gecode used to report this value in the statistics, but now it
> seems there
>> is a specific class CloneStatistics which should be updated as search
> proceeds. I
>> fail to see how to pass an object of type CloneStatistics to the DFS
> search
>> object. Also the
>> Space::clone() member function (which seems to be the only place where
> this
>> object can be updated) is not virtual, and therefore cannot be intercepted
> in my
>> subclass of Space (is this correct?). So I tried another approach, which
> was
>> simply to count the number of times that my
>> copy() function gets called, which I thought should tell me the number of
> clones.
>> Now I think I'm wrong since this number always reports the same number of
>> clones for different values of c_d.
>>
>> Obviously I'm making some mistake. Any hints?
>>
>> Thanks!
>>
>> _______________________________________________
>> Gecode users mailing list
>> users at gecode.org
>> https://www.gecode.org/mailman/listinfo/gecode-users
>
> Marco Correia <mailto:marco.v.correia at gmail.com>
> June 1, 2012 5:53 PM
> Hi,
>
> I suspect the answer to the following question should be somewhere in 
> the MPG document, but I was unable to find it - apologies if this is 
> the case.
>
> I am interested on obtaining the number of clones for a specific 
> example when subject to different value for the c_d parameter in the 
> context of a DFS search. I believe gecode used to report this value in 
> the statistics, but now it seems there is a specific class 
> CloneStatistics which should be updated as search proceeds. I fail to 
> see how to pass an object of type CloneStatistics to the DFS search 
> object. Also the Space::clone() member function (which seems to be the 
> only place where this object can be updated) is not virtual, and 
> therefore cannot be intercepted in my subclass of Space (is this 
> correct?). So I tried another approach, which was simply to count the 
> number of times that my copy() function gets called, which I thought 
> should tell me the number of clones. Now I think I'm wrong since this 
> number always reports the same number of clones for different values 
> of c_d.
>
> Obviously I'm making some mistake. Any hints?
>
> Thanks!
> Marco Correia <mailto:marco.v.correia at gmail.com>
> June 1, 2012 4:42 PM
> Hi,
>
> I suspect the answer to the following question should be somewhere in 
> the MPG document, but I was unable to find it - apologies if this is 
> the case.
>
> I am interested on obtaining the number of clones for a specific 
> example when subject to different value for the c_d parameter in the 
> context of a DFS search. I believe gecode used to report this value in 
> the statistics, but now it seems there is a specific class 
> CloneStatistics which should be updated as search proceeds. I fail to 
> see how to pass an object of type CloneStatistics to the DFS search 
> object. Also the Space::clone() member function (which seems to be the 
> only place where this object can be updated) is not virtual, and 
> therefore cannot be intercepted in my subclass of Space (is this 
> correct?). So I tried another approach, which was simply to count the 
> number of times that my copy() function gets called, which I thought 
> should tell me the number of clones. Now I think I'm wrong since this 
> number always reports the same number of clones for different values 
> of c_d.
>
> Obviously I'm making some mistake. Any hints?
>
> Thanks!
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20120602/bc447f8c/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: postbox-contact.jpg
Type: image/jpeg
Size: 1174 bytes
Desc: not available
URL: <http://www.gecode.org/pipermail/users/attachments/20120602/bc447f8c/attachment.jpg>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: compose-unknown-contact.jpg
Type: image/jpeg
Size: 770 bytes
Desc: not available
URL: <http://www.gecode.org/pipermail/users/attachments/20120602/bc447f8c/attachment-0001.jpg>