[gecode-users] Strange branching behaviour when using FunctionBrancher

[Andrea Peano]

Thank you, this should be the perfect way!

Cheers,
Andrea

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

> Hi Andrea,
>
>
>
> What you have to do is two things, basically:
>
> 1. (as mentioned) implement a brancher yourself.
>
> 2. Information that is expensive (oe even impossible)  to re-compute you
> should store in  a subclass of Choice that you yourself can define. I think
> Chapter 19 (Section 19.4) is a nice example: there the brancher also does
> symmetry-breaking during search and it stores all symmetry information
> explicitly.
>
>
>
> Cheers
>
> Christian
>
>
>
> --
>
> Christian Schulte, Professor of Computer Science, KTH,
> www.gecode.org/~schulte/
>
>
>
> *From:* Andrea Peano [mailto:andrea.peano at unife.it]
> *Sent:* Tuesday, September 23, 2014 2:31 PM
> *To:* Christian Schulte
> *Cc:* users at gecode.org
>
> *Subject:* Re: [gecode-users] Strange branching behaviour when using
> FunctionBrancher
>
>
>
> I'm sorry for multiple replies, but I want to ask this in a more general
> fashion.
>
>
>
> Consider I planned to perform a quite burdensome heuristic in a particular
> point of the search (that's why I'm splitting the search).
>
> Obviously this heuristics helps to prune the search space.
>
> How can I be sure that this heuristic is not recomputed more and more?
>
>
>
> Thanks,
>
> Andrea Peano
>
>
>
> On Tue, Sep 23, 2014 at 2:24 PM, Andrea Peano <andrea.peano at unife.it>
> wrote:
>
> 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
>
>
>
>
>
> --
>
>
>
> 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/24d84bae/attachment.html>