[gecode-users] Independent subproblems

[Malcolm Ryan]

On 23/11/2007, at 8:35 PM, Guido Tack wrote:

> Malcolm Ryan wrote:
>
>> Do you happen to know if anyone has done any work on splitting a
>> problem into independent subproblems? Eg, if I have two problems
>> which share a single variable X, then after I assign a value to X, I
>> am able to solve each of the two subproblems in isolation so it would
>> make sense to search them individually, so that failures in one don't
>> undo variable bindings in the other.
>
> We're working on it, you will be able to download a paper on it  
> soon.  We have a prototype implementation for the C++ version of  
> Gecode.  In theory, what you describe is exactly AND/OR tree  
> search.  The AI journal paper by Dechter and Mateescu (http:// 
> www.ics.uci.edu/%7Ecsp/r126.pdf) should give a sufficient overview,  
> but little detail as it comes to implementing the ideas in a real  
> CP system.

Thanks. I've been reading the Handbook of Constraint Programming some  
more. I saw it suggested somewhere in there (I've lost the reference)  
that conflict-directed backjumping (Prosser 1993) is particularly  
effective on problems of this sort. Does Gecode implement any kind of  
backjumping? Or least-discrepancy search?

Malcolm

--
Many clever men like you have trusted to civilisation.
Many clever Babylonians, many clever Egyptians,
Many clever men at the end of Rome.
                               - G.K.Chesterton, The Napoleon of  
Notting Hill