

![0_image_0.png](0_image_0.png)

mains4**. The self-avoiding walk is modeled by a sequence of binary neighboring**
constraints (ensuring the connectivity of successive monomers) **and a global** Alldifferent **constraint for self-avoidingness. Supporting decomposition of the** Alldifferent **propagator, see Sec. 5, is therefore essential for profiting from DDS.**
CPSP uses a database of pre-calculated point sets, called H-cores, that represent possible optimal distributions of H-monomers. By that, the **optimization**
problem is reduced to a satisfaction problem for a given H-core, if H-variables are restricted to these positions. For optimal H-cores, the solutions of the CSP are optimal structures. Thus, for counting all optimal structures, one iterates through the optimal cores.

The test sets**. We generated two test sets, PS-48 and PS-64, with uniformly** distributed random HP-sequences of length 48 and 64. For the generation we used the free available CPSP implementation [7]. With only minimal modifications (new branching) we use the existing CSP model with DDS.

PS-48 contains 6350 HP-sequences and for each up to 1 million optimal structures in the cubic lattice were predicted. For the 2630 HP-sequences in PS-64 up to 2 million structures have been predicted in the cubic lattice, due **to the** increasing degeneracy in sequence length. Results**. The average ratio results are given in Tab. 2. There, the enormous** search tree reduction with an average factor of 11 and 25 respectively is shown. The reduction using DDS compared to DFS leads to much less propagations (3to 5-fold). This and the slightly less fails result in a runtime speedup of **3-/4-fold** using the same variable selection heuristics for both search strategies. Here, the immense possibilities of DDS even without advanced constraint-graph specific heuristics are demonstrated. This also shows the rising advantage **of DDS over** DFS for increasing problem sizes (with higher solution numbers).