[gecode-users] Skipping branching alternatives?

[Luis Quesada]

Martin Mann wrote:

> Uff... what a discussion!
>
> thanks a lot! to give you a deeper look about my setting and what i 
> want here a short description:
>
> i ve got a Branching "MartinsBranching" == MB.
> this produces 2 types of branching descriptions: the standard 
> PosValDesc == PVD and my own with multiple alternatives == MBD
>
> during the branching i decide on some special properties of the 
> subproblem if i will branch into 2 (via PVD) or more subtrees (MBD). 
> the corresponding branching description is returned.
>
> i ve got a global structure (accessible directly via my subclass of 
> Space i am using in my problem) that handles the solution recognition.
>
> my MBD is able to detect if it is asked to commit a new branching 
> alternative or is just doing recomputation. if asked for a new branch 
> it checks if in the last branch a special solution was found. if thats 
> the case it should skip this and the following alternatives of this MBD.
>
> you see i can detect very clear the choice point where i want to skip 
> the remaining. as discussed here, it is not possible to prune the 
> alternatives via propagation because during bracktracking and new 
> branching this values might be needed.
> also i dont think it is neccessary to rewrite the search engine, 
> because the branching can do. the problem that appear is the cloning 
> of some unneccessary Spaces in the search function that calls the 
> branching::commit(..).
>
> so i agree with guido: it is not global enough for a BAB and not local 
> enough for a propagator.
> but a new search engine? ;) i am not frightened about (i ve done it in 
> the beginning..) but hope i dont need it.. i want to keep the gecode 
> changes as small as possible!
>
> hope this makes it clear
>
> my current way:
> - currently my MB::commit(..) returns ES_FAILED, if it detects the 
> question for a new branching alternative and the last branchings have 
> leaded to a special solution.
> (i wrote it doesnt function but actually right now i found the bug in 
> my code.. ;) now it works fine)
>
> so the last open question is: any alternatives for skipping?
>
> the only one i see:
> a) writing a new search engine that tests for skipping itself and 
> removes the branching description directly
>
> anything else?
>
> so thanks for your patience and support, and that you ve read until here!
>
> martin
>
Dear Martin,

The basic problem I have with the description of your problem is that it 
is too attached to the implementation....If you describe your *problem* 
without referring to your implementation, that would certainly help me.
I thought that you simply wanted to impose conditional constraints 
(e.g., W>2&Y>3 => X\=4 (because the solution you have involving X=4 
under  W>2&Y>3 is already good enough)) each time you find a solution in 
order to discard branches that (from your expert point of view) may not 
lead to better solutions.
But I now I realize that I have completely missed the point...
Anyway, I have also enjoyed the discussion (and learned from it)!
Cheers,
Luis