Search Combinators

This work introduces search combinators, an approach to modeling search in constraint solvers that enables users and system developers to quickly design complex efficient search heuristics.

For the user, we provide a compositional approach for expressing complex search heuristics based on an (extensible) set of primitive combinators. Even if the users are only provided with a small set of combinators, they can already express a vast range of combinations. Moreover, programming search in terms of combinators is far more productive than resorting to a low-level language.

For the system developer, we show how to design and implement modular combinators. Developers do not have to cater explicitly for all possible combinator combinations. Small implementation efforts result in providing the user with a lot of expressive power. Moreover, the cost of adding one more combinator is small, yet the return in terms of additional expressiveness can be quite large.

  • Search Combinators, T. Schrijvers, G. Tack, P. Wuille, H. Samulowitz, P. Stuckey. Full paper. Accepted at CP 2011. Download pdf
  • Memoizing a Monadic Mixin DSL, P. Wuille, T. Schrijvers, H. Samulowitz, G. Tack, P. Stuckey. Full paper. Accepted at WFLP 2011. Download pdf
  • Search Combinators, T. Schrijvers, G. Tack, P. Wuille, H. Samulowitz, P. Stuckey. Late breaking abstract at CPAIOR 2011. Download pdf

Our benchmark suite contains a set of MiniZinc problem models with a search specification using our combinator language.

  • practical benchmarks:
    • golfers.mzn
    • golomb.mzn
    • open_stacks.mzn
    • radiation(5,15).mzn
  • artificial stress tests:
    • bab_real.mzn
    • bab_restart.mzn
    • for+copy.mzn
    • once_sequence.mzn
    • ortest(10,20).mzn