Source-linked AI summary
Algorithm Selection for Combinatorial Search Problems: A Survey
Lars Kotthoff
TL;DR
The paper addresses how to select suitable algorithms for individual problems rather than relying on one method, focusing on combinatorial search. It surveys and classifies practical Algorithm Selection approaches, finding that systems can achieve performance close to consistently choosing the best algorithm, while noting theoretical and analysis-time limitations.
Problem
Algorithm Selection matters because different algorithms perform best on different problems, and the broad literature requires a focused synthesis for combinatorial search.
Method
The survey organises Algorithm Selection research by practical system criteria, comparing models, learning techniques, and ways of applying selection across combinatorial search problems.
Results
Some Algorithm Selection systems have come very close to always choosing the best algorithm, and many surveyed publications report performance improvements across different problems.
Takeaways & Limitations
Algorithm Selection is a practical and active research area whose systems exploit portfolio diversity to improve performance on combinatorial search problems.
Takeaways & Limitations
Selection can be constrained by analysis cost, while theoretical results imply that gains on some problems may be offset by losses on others.
Abstract
from arXiv · showhide
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 paper contrasts and compares different methods for solving the problem as well as ways of using these solutions. It closes by identifying directions of current and future research.
1. Introduction
The Algorithm Selection Problem selects algorithms case by case because different approaches perform best on different problems. This survey focuses on combinatorial search, organising practical approaches around the models, criteria, and techniques used to make such selections.
- Motivation: New algorithms often improve the state of the art only on some problems, making case-by-case selection a way to improve practical performance.Such differences can arise from heuristics or assumptions that fail on particular problem types or environments.
- Rice’s framework: Rice’s basic model maps each problem-algorithm pair to performance, then uses that mapping to choose an algorithm for a given problem.The framework identifies selection criteria including best selection across all mappings, problem subclasses, mapping subclasses, and algorithm subclasses.
- Practical models: The theoretically best mapping may be undecidable or fail to generalise, so practical systems may prefer mappings that perform well on new problems.The existence and uniqueness of an optimal mapping are usually less important than finding a useful mapping that improves current performance.
- Practical models: Including problem features makes the selection mapping identifiable in practical systems and is often the crucial step toward feasibility.Poorly representative samples or features that fail to separate problem classes can prevent a good mapping from being found.
- Scope and limitations: Selection systems target performance rather than explanations, while No Free Lunch results imply that gains on some problems can be offset by losses on others.The survey notes that the applicability of these theorems is controversial and outside its scope, although many surveyed systems improve performance across problem ranges.
- Scope and organisation: Algorithm Selection is broadly applicable, but this survey restricts its synthesis to combinatorial search problems, where substantial performance improvements have been reported.The paper uses an approach-centric organisation, so one publication may appear in multiple sections to illustrate different aspects.
2. Algorithm portfolios
Algorithm portfolios address the poor cross-problem generality of single algorithms by selecting or combining methods case by case. The survey distinguishes static portfolios, whose fixed algorithms are chosen offline, from dynamic portfolios that adapt composition or configuration to each problem.
- A portfolio mitigates the restriction that no single algorithm is likely to suit every problem by enabling case-by-case algorithm selection.This idea corresponds to the algorithm space in Rice’s framework.
- Algorithm portfolios were formalised by Huberman, Lukose, and Hogg for graph colouring and later popularised in AI by Gomes and Selman.
- Static portfolios: Static portfolios have a fixed, finite, known algorithm space whose algorithms and parameters do not change during solving.Examples include SATzilla, AQME, CPhydra, ArgoSmArT, and BUS.
- Static portfolios: Portfolio sizes range from two algorithms in one system to 60 in ArgoSmArT, with other examples using five, six, 16, or 19 algorithms.
- Static portfolios: Static portfolio success depends on choosing complementary algorithms, and random selections from a diverse pool can outperform portfolios containing the best overall performers.
- Dynamic portfolios: Dynamic portfolios adapt their composition or constituent algorithms to the problem, including by combining building blocks, specialising operators, or tuning parameters.Hydra and ISAC use parameter-tuning approaches to construct static portfolios, while more recent work also exploits parallelism.
3. Problem solving with portfolios
Using a portfolio requires decisions about which algorithms to run, how to allocate resources, and when to revise selections. Approaches range from one-shot selection to scheduled or online switching, trading simplicity against resilience and overhead.
- Portfolio use requires choosing an algorithm subset and deciding whether selection occurs once before solving or continuously during search.
- What to select: Selecting one algorithm for the entire problem is simple, but a wrong choice leaves the system stuck even when other portfolio algorithms would perform much better.
- What to select: Scheduling distributes resources across portfolio algorithms through sequential, interleaved, or parallel execution rather than committing to one solver.
- What to select: Past-performance ordering with equal time allocation achieved the best overall performance among the evaluated Pulina–Tacchella scheduling strategies.
- What to select: An evaluated schedule that ran the predicted best algorithm for 90% of available time and distributed 10% among others had the best overall performance.
- When to select: Online selection permits finer-grained decisions and can reduce the consequences of a bad choice, but selecting more frequently adds overhead.
- When to select: Switching inference methods can achieve the search-space reduction of a more expensive method at significantly lower cost by detecting cases where extra inference does not help.
4. Portfolio selectors
Portfolio selectors choose algorithms from a candidate set using performance models, learned or hand-crafted, while balancing prediction quality against selection overhead. The literature also explores hierarchical decisions and training strategies that improve predictions under specific conditions.
- Selectors choose a portfolio algorithm for each problem, often using features to identify the individual best performer rather than model exact performance values.
- Selection overhead must remain cheaper than solving the problem, motivating pre-solvers and analysis-time prediction for systems such as SATzilla.
- Using misclassification penalties during training improves prediction quality by emphasizing mistakes with large potential runtime costs.
- Selector implementations range from explicit procedures to rules embedded in compiled or evolved programs.
- Machine Learning models are commonly trained from portfolio runs on representative problems, although training can require substantial time.
- Hierarchical models can improve selection by making intermediate predictions, but their applicability is limited to relatively few scenarios.
5. Features
Features describe problems, algorithms, search behavior, or environments and may be computed before or during search. Their specificity and timing shape model applicability, overhead, and the ability to respond to unexpected behavior on the current problem.
- Features characterize inputs and support learning the relationship between a problem and an algorithm’s expected performance.
- Feature choices vary from general measures requiring little domain knowledge to highly domain-specific descriptors that can improve predictive models.
- Static features are computed before search, whereas dynamic features are gathered during search and can reflect performance on the current problem.
- Some systems use runtime distributions to allocate resources among algorithms instead of selecting a single algorithm.
- Search-progress features can avoid heavy domain knowledge but assume anytime algorithms and do not apply when only one solution is sought.
- Common combinatorial-search features include counts of variables, clauses, constraints, goals, typed structures, and ratios or summary statistics.
- Successful systems mainly gain performance from selecting the right algorithm through probing, while reusing explored search regions has received little research attention.
6. Application domains
Algorithm Selection has been applied across mathematics, software design, Machine Learning, simulation, and many combinatorial-search domains. Although the overall approach transfers across domains, implementations often require domain-specific features and may not generalize equally well.
- Applications span differential equations, linear algebra, linear systems, software algorithms and data structures, Machine Learning, explanation problems, parallel reduction, and simulation.
- Combinatorial-search applications include SAT, constraint programming, quantified Boolean formulae, combinatorial auctions, Mixed Integer Programming, set covering, and planning.
- Researchers commonly adapt systems to domains using features such as the numbers of constraints and variables.
- Domain features can be exchanged for features from another application, but acceptable cross-domain performance remains an empirical question.
- Some approaches are tailored so strongly to one application domain that they cannot be used in others.
7. Current and future directions
Current and future work extends Algorithm Selection across learning choices, parallel execution, new domains, and software construction. Key challenges include limited competitiveness of direct complex-output prediction and hardware-dependent portfolio design.
- Machine Learning: Research is exploring Machine Learning techniques that predict complex outputs such as schedules, although reported results are not competitive with other approaches.Earlier work mainly predicts the best algorithm or its performance, then derives schedules from those predictions.
- Machine Learning: There is little research on choosing the type of Machine Learning for Algorithm Selection, despite changes in the learning method used by systems such as SATzilla.This direction concerns selecting an appropriate learning paradigm rather than only applying generic Machine Learning techniques.
- Exploitation of parallelism: Parallel Algorithm Selection must account for the fact that a good portfolio changes with the number of processors available.Research is beginning to exploit multicore hardware explicitly, alongside technical considerations.
- Exploitation of parallelism: Specialised processing units such as GPUs can restrict how portfolio algorithms are run in parallel.The survey identifies this as a largely ignored challenge that may become more prominent as GPU capability increases.
- Application to new domains: Algorithm Selection is being applied to additional domains, including Answer Set Programming, as more research communities recognise its potential benefits.The survey also describes software construction as a new context with potential for higher performance improvements.
- Application to new domains: Integrating Algorithm Selection techniques into mainstream programming languages and software development systems is identified as a direction for further research.This extends Algorithm Selection beyond specialised applications and into software construction.
8. Summary
Algorithm Selection commonly learns problem–algorithm performance relations and uses portfolios, prediction, and adaptive execution strategies. Despite theoretical difficulty, surveyed systems achieve strong practical performance, while the survey abstracts a large literature into operational criteria.
- Summary: Algorithm Selection has produced significant performance improvements for combinatorial search problems, often using Machine Learning to learn problem–algorithm performance relations.The survey notes that these improvements can often be obtained with relatively little effort.
- Summary: Dozens of systems demonstrate that Algorithm Selection can succeed in practice despite its theoretical difficulty.Some systems come very close to always choosing the best algorithm.
- Summary: The survey introduces a high-level categorisation based on criteria that determine Algorithm Selection systems in practice.This categorisation abstracts from low-level details to clarify underlying principles.
- Portfolios: Portfolios may be static or dynamically augmented, and can be designed for complementarity, automatically tuned, or assembled from existing algorithms.Dynamic portfolios may combine algorithmic building blocks while problems are being solved.
- Selection and execution: Selection may choose one algorithm, several algorithms for parallel or scheduled execution, switching strategies, or the full portfolio with varied resource allocation.These alternatives differ in how many algorithms are run and how resources are assigned.
- Selection and execution: Algorithm Selection can operate offline or online, including monitoring performance, repeating selection during search, skewing schedules, or deciding when to restart.Online approaches react to observed performance or predefined decision points.
- Performance modelling: Performance models may predict the best portfolio algorithm, each algorithm’s performance, or intermediate quantities used to facilitate selection.Models can be learned automatically, hand-crafted, trained separately, or updated incrementally during solving.
- Performance modelling: Features from algorithms, problems, or runtime environments support performance modelling and may be computed before or during solving.Feature selection is commonly used to identify important and relevant features.