Algorithm Selection for Combinatorial Search Problems: A Survey

By Lars Kotthoff. The AI Magazine, 2012

403 citations recorded by the source corpus.

The Algorithm Selection Problem is concerned with selecting the best algorithm to solve a given problem on a case-by-case basis. It has become especially relevant in the last decade, as researchers are increasingly investigating how to identify the most suitable existing algorithm for solving a problem instead of developing new algorithms. This survey presents an overview of this work focusing on the contributions made in the area of combinatorial search problems, where Algorithm Selection techniques have achieved significant performance improvements. We unify and organise the vast literature according to criteria that determine Algorithm Selection systems in practice. The comprehensive classification of approaches identifies and analyses the different directions from which Algorithm Selection has been approached. This chapter contrasts and compares different methods for solving the problem as well as ways of using these solutions.

Subfields: Artificial Intelligence, Computer Networks and Communications, Signal Processing

View Paper: https://www.semanticscholar.org/paper/9579a0ba622f4d4a7e158d76eaaf7bb2014419e6

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Signal Processing

Citations in the corpus

Learning Performance-Improving Code Edits (2023, methodology): “, 2021), automatic algorithm selection (Kotthoff, 2016; Kerschke t al., 2019), and room at the top (Leiserson t al.”
Algorithm runtime prediction: Methods & evaluation (2012, methodology): “, 2014b] basis [Rice, 1976; Smith-Miles, 2009; Kotthoff, 2014] has been successfully addressed by using EPMs to predict the performance of all candidate algorithms and selecting the one predicted to perform best [Brewer, 1995; Lobjois and Lemaı̂tre, 1998; Fink, 1998; Howe et al.”
Solving Mixed Integer Programs Using Neural Networks (2020, background): “• Miles Lubin for providing help with PySCIPOpt and references for Algorithm Configuration and Algorithm Selection.”
Alors: An algorithm recommender system (2017, methodology): “The advances of algorithm selection in SAT and CP in the last decade rely on two facts (Kotthoﬀ, 2014).”
Efficient Parameter Importance Analysis via Ablation with Surrogates (2017, methodology): “Before EPMs were used in algorithm configuration, they were already a key technique in perinstance algorithm selection (see, e.g., Rice 1976, Kotthoff 2014); furthermore, they have recently been used to define surrogate benchmarks for efficient benchmarking of hyperparameter optimization tools…”
Automated Algorithm Selection: Survey and Perspectives (2018, methodology): “Over the years, algorithm selection techniques have achieved remarkable results in several research areas – especially for discrete combinatorial problems (see, e.g., Smith-Miles, 2009; Kotthoff, 2014).”
A Tutorial On the design, experimentation and application of metaheuristic algorithms to real-World optimization problems (2021, background): “…dedicate some closing words to the ﬁeld of meta-learning, which is understood as the family of methods aimed at inferring a potentially good algorithm for a given problem without actually addressing it, namely, just by the similarities of the problem with others tackled in the past [153, 154].”
Auto-Sklearn 2.0: Hands-free AutoML via Meta-Learning (2020, methodology): “However, treating the choice of model selection strategy as an algorithm selection problem allows us to apply methods from the field of algorithm selection (Smith-Miles, 2008; Kotthoff, 2014; Kerschke et al., 2019) and we can in future work reuse existing techniques besides the pairwise classificati”
Algorithm Runtime Prediction: Methods and Evaluation (Extended Abstract) (2015, methodology): “This classic problem of selecting the best from a given set of algorithms on a per-instance basis [Rice, 1976; Smith-Miles, 2009; Kotthoff, 2014] has been successfully addressed by using EPMs to predict the performance of all candidate algorithms and selecting the one predicted to perform best…”