[gecode-users] Strange branching behaviour when using FunctionBrancher

[Andrea Peano]

On Tue, Sep 23, 2014 at 2:09 PM, Christian Schulte <cschulte at kth.se> wrote:

> You can disable recomputation but this is not a good idea as it degrades
> performance seriously and increases memory consumption considerably.
>
Yes, I see.


>
>
> What you could do (also not good) is call status() yourself.
>
I'm already doing it, but this does not seem enough to prevent
recomputation on those nodes. I call it within second_level and third_level
but it's not enough. Do you mean somewhere else?


>
>
> The real (but tough) thing to do is to implement your own brancher.
>

>
> And just checking: do you know that multiple branchers are executed in the
> order they are created? But maybe that is not enough for you.
>
Yes, I know, I tried to make the search as simple as possible, but there
are some aspects of the problem a bit difficult to manage.
Anyway, I'll find a way.

Thanks for giving me a halping hand.

Andrea


>
>
> Cheers
>
> Christian
>
>
>
> --
>
> Christian Schulte, Professor of Computer Science, KTH,
> www.gecode.org/~schulte/
>
>
>
> *From:* users-bounces at gecode.org [mailto:users-bounces at gecode.org] *On
> Behalf Of *Andrea Peano
> *Sent:* Tuesday, September 23, 2014 2:00 PM
> *To:* users at gecode.org
> *Subject:* Re: [gecode-users] Strange branching behaviour when using
> FunctionBrancher
>
>
>
> I was just reading on the Gecode guide that this behaviour is due to the
> "recomputation".
>
> So I have two more questions: can I completely prevent this behaviour by
> disabling recomputation?
>
> Has recomputation a direct effect on parallel search?
>
>
>
> Thanks,
>
> Andrea
>
>
>
> On Tue, Sep 23, 2014 at 1:22 PM, Andrea Peano <andrea.peano at unife.it>
> wrote:
>
> Hello,
>
>
>
> I've implemented a search strategy by splitting the search into three
> levels. I think the code may explain better this strategy.
>
>
>
>
>
> void MyModel::post(Space& home)
>
> {
>
> static_cast<MyModel&>(home).second_level();
>
> }
>
>
>
> void MyModel::second_level()
>
> {
>
> status();
>
>
>
> //do something with the partial solution
> //print "second level"
>
> branch(*this, BoolBranchDirection, INT_VAL_MIN());
>
> branch(*this, post2);
>
> }
>
>
>
> void MyModel::post2(Space& home)
>
> {
>
> static_cast<MyModel&>(home).third_level();
>
> }
>
>
>
> void MyModel::third_level()
>
> {
>
> if(BoolBranchDirection.val()==0)
> {
> //print third level left
> //left branch behaviour (install further branches)
> }
> else
> {
> //print third level right
> //right branch behaviour (install further branches)
> }
>
> }
>
>
>
> Imagine now we are fixing the partial solution before the "post" calling,
> so the solver goes only once into the "post" function (and it's confirmed
> by GIST).
>
>
>
> The strange fact is that "second_level" is called more than once! Instead
> I expect one call for "second_level" and two calls for "third_level", which
> executes two different paths of the code.
>
>
>
> These are the prints I read:
>
> second level
>
> third level left
>
> second level
>
> third level right
>
> second level
>
> third level right
>
>
>
> But I expected:
>
> second level
>
> third level left
>
> third level right
>
>
>
> Can you clarify this behaviour please?
>
>
>
> Furthermore, I experienced that I need to call "status()" within the
> second level, to ground some variables I expected to be already ground. Is
> this normal?
>
>
>
> I'm using Gecode 4.2.1
>
>
>
> Thanks,
>
> Andrea
>
>
>
>
>
> --
>
>
>
> Andrea Peano - PhD student
>
> Department of Engineering - University of Ferrara
>
> Tel: +39 0532 97 4827
>
>
>
>
>
> --
>
>
>
> Andrea Peano - PhD student
>
> Department of Engineering - University of Ferrara
>
> Tel: +39 0532 97 4827
>



-- 

Andrea Peano - PhD student
Department of Engineering - University of Ferrara
Tel: +39 0532 97 4827
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20140923/ba05d551/attachment-0001.html>