[gecode-users] Skipping branching alternatives?

[Luis Quesada]

Guido Tack wrote:

>Am Montag, 10. Juli 2006 15:37 schrieb Luis Quesada:
>  
>
>>>Cutting off branches is normally considered part of exploration. [...]
>>>      
>>>
>>I don't agree with this bit Guido. Cutting off branches (i.e. pruning)
>>is the very purpose of propagation. When you remove 5 from X's domain
>>you are cutting off the branch associated with X=5.
>>    
>>
>
>Ok, maybe I wasn't clear enough. Typically, you specify your constraint 
>problem using propagators and branchings, and this totally determines the 
>shape of your search tree. Now, some sophisticated search engines prune the 
>tree during search, e.g. B&B and SBDS. Of course, these engines post new 
>constraints to do the actual pruning, which can be implemented as propagators 
>or may just be basic tells.
>
>Encoding a pruning of the tree into the initial model seems a bit weird - the 
>model doesn't define a unique search tree any more.
>
>  
>
OK. I see the point that you, Mikael and Martin are making.

Actually, what I had in mind is a  kind of adaptative branch and bound 
where you update the order constraint on the fly based on the solution 
you have just found (which  actually follows the same idea of SBDS).

Cheers,

Luis