[gecode-users] Skipping branching alternatives?

[Christian Schulte]

I just reply to this email, even though I have read the discussion. I very
much second Guido and Mikael and I have another bit to add as to why your
idea of tinkering with branchings does not work.

The entire setup of search in Gecode relies on recomputation: here, a commit
operation using a branching description _must_ always tell the very same
constraint when invoked with the same parameters. So by definition, it is
not allowed to use state in the way you state it.  

Christian

--
Christian Schulte, http://www.imit.kth.se/~schulte/ 

-----Original Message-----
From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf
Of Martin Mann
Sent: Monday, July 10, 2006 2:27 PM
Cc: gecode user list
Subject: Re: Re: [gecode-users] Skipping branching alternatives?



Hi Luis,

the idea with the propagator is nice, but not possible in my situation i 
think. i dont want a "static" alternative-skipping.. that's easy to do 
with propagators, you are right. but i want to do a "dynamic" one. i am 
not interested in all solutions of the search tree and i dont have a 
real deterministic branch and bound strategy at hand. that's why i want 
to do a dynamic skipping of branches during the search.

e.g. the situation is like that: i find a special "interesting" solution 
in this branch and and i dont want to have a look in the remaining 
branches that belong to my specialised branching description (i mix them 
with normal ViewValBranchingDescr during the branching). so i would like 
to cut some subtrees of the the search tree that belong to my branching 
descriptor.

i tried the first idea i mentioned (just return ES_FAILED from the 
commit(..) function) to skip the alternatives, but this results in 
abnormal behavior. dont know why at the moment and didnt had a closer 
look until now.

so my question again, is there another possibility? or do i ve got to do 
  it bruteforce via clearing one domain to let the propagators do the 
work for me?
anyway i m still interested in skipping the remaing more directly but 
without reimplementing DFS myself.. ;)

thanks a lot, i hope i made it a bit clearer

martin


Luis Quesada wrote:
> I don't understand why you need to do this... To me, eliminating
> branching alternatives is the very purpose of propagators. Why don't you 
> implement a propagator that removes the alternatives you want to skip? 
> As you build the branches at each branching step based on the current 
> domains of the variables, you wont try the alternatives that you want to 
> skip.
> 
> Luis
> 
> Martin Mann wrote:
> 
>> Hi again,
>>
>> I ve got a question about Branching..
>>
>> I implemented my own Branching inclusive a branching descriptor that
>> supports more than 2 alternatives.
>>
>> During my branching sometimes I would like to skip the remaining
>> alternatives.
>> So my question:
>>
>> 1) is it ok just to return ES_FAIL from MyBranching::commit(..) to
>> skip the corresponding branch? or will it lead to some strange behavior?
>>
>> 2) is there a possibility for directly skipping the remaining
>> alternatives without implementing the whole search engine? I would 
>> like to use DFS as it is.. ;)
>>
>> thanks lot and have a nice weekend
>>
>> Martin
>>
>>
>> _______________________________________________
>> Gecode users mailing list
>> users at gecode.org https://www.gecode.org/mailman/listinfo/gecode-users
> 
> 
> 

_______________________________________________
Gecode users mailing list
users at gecode.org
https://www.gecode.org/mailman/listinfo/gecode-users