[gecode-users] Decomposition during search

[Guido Tack]

Malcolm Ryan wrote:

> Did the experimental Decomposition during search code make it into the
> 2.2.0 release of Gecode? I would like to take advantage of it on my
> current constraint problem. If it is there, is there any description
> of how it works?

Sorry, DDS was planned to be included in 3.0, but it won't make it, as  
the implementation relied on reflection, which won't be in 3.0.  The  
problem is that the decomposition analysis has to look at the  
constraint graph, and so far reflection was the only way to implement  
that (and not a very efficient way after all).

We have several other analyses that we hope to integrate in a future  
version of Gecode, but we first have to come up with a simple and  
efficient interface to the constraint graph.

> Would it work with a custom Branching? I'd like to still be able to
> control the order variables in each sub-problem are assigned and the
> values they are given.

Yes, in principle it will work with a custom branching, as long as it  
is a ViewValBranching.  DDS was actually implemented as a wrapper  
branching around a ViewValBranching.

> Is there any simple way to measure the 'decomposability' of my
> problem? I have an intuition that my problem will split into many
> small independent sub-problems as search proceeds, but it is too large
> and complex to check this by hand.

You could check out revision 8076 of the trunk.  That revision should  
have a working version of DDS (though it's not fully tested).  You can  
take the function connectedComponents from gecode/dds/decomposing- 
branching.hpp to analyse your problem, e.g. every time your copy  
function is called.

Cheers,
	Guido