[gecode-users] Skipping branching alternatives?

[Martin Mann]

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



Guido Tack schrieb:
>> I do not know whether BAB will be good enough as I do not know what Martin
>> exactly needs. However I would also supsect that it will be BAB + X, where
>> X might be to get more information from search so far.
> 
> I thought about that a bit yesterday, and BAB seems to be not enough. The 
> problem is that you cannot express the pruning as a single constraint. E.g., 
> if you find some solution with x=4 and want to prune all branches one level 
> above that solution that have x!=4. Then you cannot simply say that x!=4 for 
> all nodes explored later.
> From what I understood, you need to limit the pruning to one particular choice 
> point, and I cannot see how to achieve that using BAB. Or, in Luis' terms, 
> the property Martin wants to express seems to be not global enough for BAB, 
> but not local enough to be addressed by branchings and/or propagators alone. 
> That's why you need a new search engine.
> 
> Cheers,
> 	Guido
>