tion of the possible branches while commit **executes the branching according to**
a given description and alternative number.

A decomposing branching in Gecode is a wrapper around a standard variablevalue branching. The actual work is done by description**: it requests the constraint graph and performs the connected component analysis. If decomposition**
is possible, a special description is returned, representing the independent subsets Xˆi ⊂ X**. Otherwise,** description **is delegated to the embedded variable-value**
branching. Note that Gecode supports n**-ary branchings, so decompositions do** not have to be binary (as presented so far).

When commit **is invoked with a variable-value description, the call is again**
delegated to the embedded branching. For a decomposition description, the branching's list of variables is updated to Xˆi for branch i**, those still active**
in the selected component.

## 6.5 Decomposition Search Engines

As decomposition is performed by the branching, the search engines have to be specialized accordingly. We developed four search engines for DDS. **A counting**
search engine computes the number of solutions of a given problem. A generalpurpose search engine allows to incrementally search the whole tree **and access all**
the partial solutions. Based on that we provide a search engine that enumerates all full solutions. A graphical search engine based on Gecode's Gist **(graphical** interactive search tool) displays the search tree with special decomposition nodes, and allows to get an overview of where and how a particular problem can be decomposed. Figure 6 shows a screen shot of a partial search using DDS. Circular nodes with inner squares represent decompositions. All search engines accept cut-off parameters for the number of (full, not partial!) solutions to be explored.

## 7 Applications And Empirical Results

To illustrate possible use cases of DDS we applied it to two counting problems with global constraints. At first, the widely known graph coloring problem allows for a good and scalable illustration of the DDS effects due to the coherence of problem and constraint graph structure. It serves therefore as a model to investigate the impact of the problem structure on DDS in the presence of global constraints. Afterwards, we study the benefit of DDS on the real world problem of optimal protein structure prediction. This problem can be modelled using constraint programming [2] but necessitates the presence of global constraints covering the whole problem. Thus, the discussed constraint decomposition is an essential prerequisite to enable DDS.

Both applications show tremendous reductions in runtime and search tree size.

The applications were realized using our DDS implementation in Gecode.

Only the search strategy was changed (DFS to DDS) - modeling, variable and value selection were kept the same for an appropriate comparison of the results.