Evolution of Algorithm Portfolio Methods for Combinatorial Search and...

The last decades have witnessed tremendous growth in the performance of solvers dealing with NP-hard problem instances. Commonly, powerful solvers outperform the other candidates for the majority of cases but obtain poor results for particular sub-domains. For this reason, Algorithm Portfolio approaches have been developed, allowing to exploit a set of solvers with complementary strengths, instead of running a single best one for all instances. Recent successful implementations combine these approaches with automatic Algorithm Configuration methods, which consider a single parameterized solver and identify the best putative values of its hyper-parameters for the analyzed instances distribution. This paper aims to illustrate the development of the principal approaches that leverage machine learning to accelerate the solution search of modern solvers. Furthermore, it presents the basic notions necessary to understand the process that enabled these techniques to achieve their amazing results with some of the many performing implementations for SAT, Answer Set Programming, and Constraint Programming.