[gecode-users] Independent subproblems

[Guido Tack]

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.

> My problem domain has this feature and I am trying to exploit it. It
> seems to me that a structural analysis of the constraint graph could
> uncover this kind of feature in general problems. I don't imagine
> this is an original idea. Has there been any work in the area?

I am not aware of any actual system that implements this.  It is  
possible to write your own search engine in Gecode that is aware of  
your problem structure and solves subproblems independently, but to  
have a fully general solution, it's necessary to get some basic  
support from the solver.

Cheers,
	Guido