Source-linked AI summary
Automated Algorithm Selection: Survey and Perspectives
Pascal Kerschke, Holger H. Hoos, Frank Neumann, Heike Trautmann
TL;DR
Because different instances favor different algorithms, automated selection seeks to exploit this complementarity. This survey synthesizes methods, features, applications, and related approaches across discrete and continuous optimisation, reporting substantial gap closure while identifying multi-objective selection as an open area.
Problem
Different instances often favor different algorithms, creating a need to determine which candidate algorithm will perform best for each instance.
Method
The survey reviews per-instance algorithm selection, its instance features, applications to discrete and continuous problems, and relationships to configuration, scheduling, and portfolios.
Results
State-of-the-art combinatorial selectors close 25%–96% of the VBS-SBS gap, while reported studies also demonstrate selection results for discrete and continuous optimisation.
Takeaways & Limitations
Informative, cheaply computable features provide the basis for effective selection, and performance complementarity offers exploitable gains across diverse problem domains.
Takeaways & Limitations
No systematic studies have addressed automated algorithm selection for multi-objective continuous optimisation problems.
Abstract
from arXiv · showhide
It has long been observed that for practically any computational problem that has been intensely studied, different instances are best solved using different algorithms. This is particularly pronounced for computationally hard problems, where in most cases, no single algorithm defines the state of the art; instead, there is a set of algorithms with complementary strengths. This performance complementarity can be exploited in various ways, one of which is based on the idea of selecting, from a set of given algorithms, for each problem instance to be solved the one expected to perform best. The task of automatically selecting an algorithm from a given set is known as the per-instance algorithm selection problem and has been intensely studied over the past 15 years, leading to major improvements in the state of the art in solving a growing number of discrete combinatorial problems, including propositional satisfiability and AI planning. Per-instance algorithm selection also shows much promise for boosting performance in solving continuous and mixed discrete/continuous optimisation problems. This survey provides an overview of research in automated algorithm selection, ranging from early and seminal works to recent and promising application areas. Different from earlier work, it covers applications to discrete and continuous problems, and discusses algorithm selection in context with conceptually related approaches, such as algorithm configuration, scheduling or portfolio selection. Since informative and cheaply computable problem instance features provide the basis for effective per-instance algorithm selection systems, we also provide an overview of such features for discrete and continuous problems. Finally, we provide perspectives on future work in the area and discuss a number of open research challenges.
1 Introduction
The survey motivates per-instance algorithm selection by performance complementarity: different algorithms excel on different instances, so no single algorithm dominates universally. It extends earlier surveys across problem domains, feature sets, and related approaches while acknowledging selective coverage.
- Motivation: Different algorithms perform best on different instance types, producing performance complementarity across many decision, optimisation, and polynomial-time problems.The survey notes that this phenomenon is distinct from the unrestricted-landscape assumptions of the no-free-lunch theorem.
- Motivation: Per-instance algorithm selection chooses, for each problem instance, the algorithm expected to perform best from a given set.The problem was identified in seminal work by Rice and later became practically tractable through subsequent methods.
- Scope and contributions: The survey distinguishes algorithm selection from configuration, schedules, and parallel portfolios while discussing their similarities and synergies.Its primary focus remains pure per-instance algorithm selection, despite complex systems combining multiple approaches.
- Scope and contributions: The survey extends previous overviews by covering algorithm selection for both discrete and continuous problems and comparing their challenges and solutions.It also addresses mixed discrete/continuous optimisation in its broader scope.
- Scope and contributions: Informative, problem-specific features are presented as a crucial basis for effective algorithm selection systems.The survey reviews promising feature sets and characteristics demonstrated to support selection.
- Scope and contributions: Because the literature is considerable and fast-growing, the survey selects contributions based on impact, promise, and conceptual contribution rather than comprehensive coverage.The authors explicitly frame the review as selective.
2 Algorithm Selection and Related Problems
Per-instance selection maps instance features to an algorithm, aiming to approach the virtual best solver while outperforming the single best solver. Related approaches differ in whether they configure, schedule, or run algorithms concurrently.
- Per-instance selection: The per-instance selection problem constructs a selector mapping each instance to an algorithm that optimizes aggregate performance under a chosen metric.The formulation uses an instance set, candidate algorithm set, and performance metric.
- Per-instance selection: Informative, cheaply computable instance features support selectors that approximate the performance of a perfect selector.Feature vectors f(i) summarize the instance for selection.
- Evaluation: The virtual best solver is a lower bound, while the single best solver is an upper benchmark for realistic per-instance selectors.The VBS chooses the best algorithm retrospectively per instance; the SBS is best overall across the set.
- Evaluation: State-of-the-art combinatorial selectors close 25%–96% of the VBS-SBS gap, whose size reflects performance complementarity.The gap measures the potential gain from instance-specific selection.
- Related approaches: Algorithm configuration can optimize exposed selector design choices for particular selection scenarios, as demonstrated by AUTOFOLIO.The per-instance variant of algorithm configuration remains an open challenge.
- Related approaches: Parallel portfolios run algorithms concurrently and can approach VBS wall-clock performance, but require parallelism proportional to the algorithm-set size.Sequential execution can incur time close to n times the VBS time.
- Related approaches: Algorithm schedules run selected algorithms sequentially for specified cutoffs and can provide effective, easier-to-implement per-set strategies.Static schedules are also used as pre-solving phases before feature-based selection.
- Selection methods: Performance prediction and cost-based classification are alternative foundations for selecting algorithms from instance information.Regression predictors estimate algorithm performance, whereas classification approaches directly support selection decisions.
3 Features for Discrete and Continuous Problems
The survey reviews informative instance features for discrete and continuous problems, emphasizing their role in automated algorithm selection and related tasks. It covers feature families for SAT, ASP, AI planning, TSP, and multi-objective continuous optimisation, while noting computational and representational limitations.
- Feature requirements: Informative, interpretable, complementary, and automatically computable features link instance characteristics to algorithm performance for algorithm selection.Redundant features can be computationally wasteful and problematic for some machine-learning methods.
- Feature types: The survey distinguishes problem-specific features, such as SAT clause counts, from generic features based on statistics from short solver probing runs.It presents these feature types as useful for algorithm selection and for understanding algorithm strengths and weaknesses.
- Discrete problems: SAT feature collections range from 91 features across nine sets to 138 features, but graph, linear-programming, probing, diameter, and survey-propagation features can be expensive to compute.Feature-computation costs may leave less time for running the selected solver and limit practical usefulness.
- Discrete problems: ASP feature sets combine SAT-related measures with ASP-specific statistics, including facts, rules, constraints, and other logic-program properties.One widely used collection contains 52 features grouped into four sets.
- Discrete problems: AI planning features describe domain and instance structure using counts, PDDL requirements, and causal-graph metrics such as vertices, degrees, and edge statistics.Earlier work began with simple counts of actions, predicates, objects, goals, and initial-state predicates before expanding to 41 features.
- Continuous problems: Multi-objective continuous optimisation still lacks mature feature characterisation because single-objective features miss objective interactions, although locally efficient sets and fronts support multimodality measures.The survey identifies interaction-sensitive techniques as a possible way to address this limitation.
4 Algorithm Selection for Discrete Problems
Discrete algorithm selection exploits complementary solver strengths across SAT, AI planning, and TSP, with systems combining instance features, learning, scheduling, and portfolios. Results include strong competition performance, although generalisation can favor dynamic scheduling on dissimilar instances.
- Discrete problems often require multiple complementary algorithms because no solver dominates across all instances.
- Propositional satisfiability and related problems: SATzilla2007 improved on SATzilla2003 by replacing ridge-regression hardness models with sparse multinomial logistic regression and winning multiple 2007 SAT Competition prizes.
- Propositional satisfiability and related problems: SNNAP predicts solver performance with random forests, finds similar training instances using Jaccard distance, and closes around 50% of the VBS-SBS gap on broad SAT benchmarks.
- AutoFolio combines algorithm selection with automated configuration by applying SMAC to the parametric CLASPFOLIO2 framework.
- AI planning: PLANZILLA substantially outperformed individual IPC-14 planners and approached the VBS, but dynamic scheduling performed better on testing instances dissimilar from training data.
- Travelling salesperson problem: Inexact TSP solving benefits from complementary state-of-the-art solvers, including EAX, LKH, and MAOS, while exact solving has long been dominated by CONCORDE.
5 Algorithm Selection for Continuous Problems
Continuous algorithm selection remains less systematically studied, but exploratory landscape analysis, feature selection, and constructed instance sets support promising selectors. On BBOB, a learned selector substantially improved relative ERT over the single best solver, while representative training data remains an open challenge.
- Continuous optimisation selection depends strongly on representative training data, whose construction remains an open challenge for benchmark-based systems.
- Unconstrained single-objective optimisation problems: A BBOB study used exploratory landscape analysis and cost-sensitive learning to predict the best algorithm among four candidate optimisers.
- Unconstrained single-objective optimisation problems: 480 BBOB instances were combined with results from 129 COCO solvers, then reduced to a carefully selected subset of 12 solvers for selector construction.
- Constrained single-objective optimisation problems: For constrained optimisation, studies investigate how features describing correlations among linear and quadratic constraints relate to solver performance.
- Constrained single-objective optimisation problems: 34 Multi-objective instance construction using constraint tradeoffs provided a better basis for algorithm selection than maximising pairwise solver-performance differences.
- Multi-objective optimisation problems: No systematic studies yet address automated selection for multi-objective continuous optimisation, although relevant feature and landscape-analysis approaches exist.
6 Perspectives and Open Problems
The survey identifies open directions spanning performance evaluation, benchmark design, online selection, mixed-problem features, and multi-objective optimisation. It emphasizes tailoring selectors and benchmarks to problem structure while addressing gaps in generalisation and feature characterisation.
- Performance measures: Performance-measure parameters can change algorithm rankings and the performance characteristics of selectors built from them.PAR10 and ERT are common measures, but altering their parameters changes how robustness and performance are evaluated.
- Evolving / generating problem instances: Solver-tailored instance generation could produce more informative benchmarks and improve selector generalisation to unseen problems.Evolved instances can be designed for diversity and relevance to a given solver set, while also revealing solver strengths and shortcomings.
- Online algorithm selection: Online algorithm selection remains underexplored relative to offline selection, although adapting choices during problem solving may yield better results.Hyper-heuristics and life-long learning approaches select or generate solvers from heuristic components, with reported results for constraint satisfaction and bin packing.
- Features for mixed (discrete + continuous) problems: Mixed discrete and continuous problems require richer features, illustrated by MIP features spanning problem structure, matrices, objectives, and LP information.The survey reports 95 MIP features and a TTP representation combining TSP, knapsack, and connecting-problem parameters.
- Algorithm selection for multi-objective optimisation problems: Multi-objective optimisation is a major uncovered application area, with limited research on features that capture interactions among competing objectives.Existing benchmarks are often artificial, and computing features independently for each objective ignores interaction effects that shape landscapes.
- Per-instance algorithm configuration: Per-instance algorithm configuration is difficult because large configuration spaces are sparsely covered by training data.Learning a mapping from instance features to configurations is challenging when training data samples only a small fraction of valid configurations.