Comparison of Hyperparameter Optimization Methods for Selecting Search Strategy of Constraint Programming Solvers

Selecting the most effective search strategy for new problems in constraint programming is a significant challenge. While autonomous search strategy design has been extensively researched, this study adopts a different approach. We present a comprehensive comparison of various hyperparameter optimization methods, treating the search strategies of constraint solvers as hyperparameters. This approach aims to enhance the selection process of search strategies, improving solver efficiency and effectiveness, and relieving the users from the burden of choosing the right one for their problems.
We introduce the probe and solve algorithm, a generic method that operates in two phases: a probing phase, where various strategies are explored and ranked using hyperparameter optimization methods, and a solving phase, where the top-ranked strategy is used to solve the problem. We include a comparative analysis between the probe and solve algorithm and the solver’s default search strategies.
Our results demonstrate that Bayesian optimization is the best hyperparameter optimization method we have tested to select the search strategy. Furthermore, it can outperform state-of-the-art dynamic search strategies across various benchmarks and solvers.
Bayesian optimization showed superior performance in 20%- 30% of cases, with both our algorithm and baselines achieving equal results in 50%-60% of instances, thus emerging as the most suited for selecting the search strategy.