Selecting Search Strategy in Constraint Solvers using Bayesian Optimization

In the field of constraint programming, selecting the most effective search strategy for a new problem is a complex task. Despite the existence of numerous autonomous search strategies, the effectiveness of a strategy is highly problem-specific and no single strategy can universally excel. Therefore, for the solver’s developers, it is difficult to find a good default strategy working across many problems. For the end-user, it is a daunting task to select the best search strategy, and they will usually rely on the solver’s default, missing out better strategies.
In this paper, we introduce the probe and solve algorithm which explores different search strategies in a probing phase, using a portion of the global timeout, and uses the best strategy found to solve the problem. By viewing the search strategy as hyperparameters, we leverage Bayesian optimization, a hyperparameter optimization technique well-known in machine learning but, to the best of our knowledge, not used in constraint programming. A key strength of our approach is to be generic and non-invasive: it can be used on top of any MiniZinc or XCSP3-compatible solvers, without modifying those. Further, probe and solve consistently achieved better results in the XCSP3 and MiniZinc competitions than the solver’s default search and modern dynamic search strategies: DomWDeg/CACD, FrbaOnDom and PickOnDom, with the ACE and Choco constraint solvers.