Adapting the search procedure and parameters dynamically during search is another promising area for future work. The solving process could be tailored to the characteristics of parts of the search space to improve efficiency.

Another direction for future work is to support a higher level of abstraction for decomposing problems into subproblems. This would be necessary to support problems which cannot be decomposed by simply adding constraints that split the domain of a variable.

## Acknowledgements

The authors thank Chris Jef ferson for help with implementing the model splitting in Minion and the anonymous reviewers for their feedback. Lars Kotthof f is supported by a SICSA studentship.

## References

1. Blumofe, R.D., Leiserson, C.E.: Scheduling multithreaded computations by work stealing. J. ACM 46(5), 720–748 (1999)
2. Collin, Z., Dechter, R., Katz, S.: On the feasibility of distributed constraint satisfaction. In: IJCAI. pp. 318–324 (1991)
3. Ezzahir, R., Bessiere, C., Belaissaoui, M., Bouyakhf, H., Mohammed, U., Agdal, V.: DisChoco: A platform for distributed constraint programming (2007)
4. Gent, I.P., Jefferson, C., Kotthoff, L., Miguel, I., Nightingale, P.: The DOMINION
input language version 0.1. CIRCA preprint 2009/21, University of St Andrews (2009), http://www-circa.mcs.st-and.ac.uk/Preprints/InLangSpec.pdf 5. Gent, I.P., Jefferson, C., Miguel, I.: MINION: a fast, scalable, constraint solver. In:
ECAI. pp. 98–102 (2006)
6. Hamadi, Y.: Disolver 3.0: the Distributed Constraint Solver version 3.0 (2007) 7. Kumar, V., Rao, V.N.: Parallel depth first search. Part II. analysis. Int. J. Parallel Program. 16(6), 501–519 (1987)
8. Lecoutre, C., Sais, L., Tabary, S., Vidal, V.: Nogood recording from restarts. In:
IJCAI'07: Proceedings of the 20th international joint conference on Artifical intelligence. pp. 131–136. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA
(2007)
9. Michel, L., Hentenryck, P.V.: A decomposition-based implementation of search strategies. ACM Trans. Comput. Logic 5(2), 351–383 (2004)
10. Michel, L., See, A., Hentenryck, P.V.: Parallelizing constraint programs transparently. In: CP. pp. 514–528 (2007)
11. Petcu, A.: FRODO: a FRamework for Open/Distributed constraint optimization.

Technical report no. 2006/001, Swiss Federal Institute of Technology (EPFL)
(2006), http://liawww.epfl.ch/frodo/
12. Rao, V.N., Kumar, V.: On the efficiency of parallel backtracking. IEEE Trans.

Parallel Distrib. Syst. 4(4), 427–437 (1993)
13. Rao, V.N., Kumar, V.: Parallel depth first search. Part I. implementation. Int. J.

Parallel Program. 16(6), 479–499 (1987)
14. Rolf, C.C., Kuchcinski, K.: Load-balancing methods for parallel and distributed constraint solving. In: CLUSTER. pp. 304–309 (2008)