[gecode-users] Strange branching behaviour when using FunctionBrancher

[Andrea Peano]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20140923/c7fddfb3/attachment-0001.html>