Adding Search to a Declarative Modelling Language

Modellers would like to automatically translate a declarative conceptual model of a constrained combinatorial problem into an efficient design model. However, for efficiency, most solving techniques require a model-specific search strategy, which is inherently procedural and, thus, difficult to integrate with the declarative conceptual model. This paper describes a small, non-intrusive extension to the declarative modelling language Zinc that achieves such an integration by providing a number of generic search patterns that take Zinc user-defined functions as parameters. We show the generality of the approach by using it to implement three very different kinds of search: backtracking search, branch-and- bound search, and local search. In each case, the work done by the modeller is small, while the performance is competitive with hand-coded search strategies. This demonstrates that search can be implemented in a manner that maintains the benefits of declarative modelling languages, while still being reasonably efficient.