When faced with NP-hard problems like Boolean Satisfiability (SAT) or the Traveling Salesperson Problem (TSP), computer scientists traditionally hunt for the single fastest algorithm. However, the No Free Lunch theorem and empirical reality throw a wrench in this pursuit: no single algorithm consistently outperforms all others across every problem instance. A solver that dominates in one domain might fail catastrophically in another due to subtle shifts in the problem's underlying structure.
As noted by O'Sullivan in Opportunities and Challenges for Constraint Programming, this performance heterogeneity creates a massive opportunity. Instead of forcing a single default solver to handle diverse workloads, we can treat the choice of algorithm itself as a computational problem. This is the core of per-instance algorithm selection: using machine learning to evaluate the features of a specific problem instance and dynamically assigning it to the most suitable solver within a portfolio.
Why It Works: Exploiting Complementarity
To understand why algorithm selection works, consider how different solvers navigate a search space. Solvers are rarely strictly better than one another; instead, they possess complementary strengths. For instance, in automated reasoning, branching heuristics are highly sensitive to instance structure, as discussed by Samulowitz et al. in Learning to Solve QBF. One heuristic might exploit tightly clustered variables, while another excels at uniform distributions.
By maintaining a diverse portfolio of algorithms, we create an envelope of peak performance that spans multiple domains. Gao et al. demonstrate this in Neural Solver Selection for Combinatorial Optimization, showing that instance-level coordination allows a meta-model to map unique structural features directly to the most effective heuristic. This approach sidesteps the need to engineer a single, omnipotent algorithm, achieving state-of-the-art results simply by routing instances to the right existing tool.
The Mechanics of Selection
How do we choose the right solver without actually running them all and incurring prohibitive computational overhead? The process relies on a three-step pipeline:
- Feature Extraction: Compute a cheap, low-dimensional representation of the problem instance (e.g., graph density, clause-to-variable ratios, or neural embeddings).
- Performance Prediction: Use a meta-model to map these features to predicted runtimes or rankings for each solver in the portfolio.
- Routing: Execute the solver predicted to be the fastest.
The predictive logic itself must adapt to the problem domain. As Lindauer details in AutoFolio: An Automatically Configured Algorithm Selector (Extended Abstract), different tasks favor different underlying models—some domains benefit from simple regression, while others require complex pairwise voting. By automatically configuring the selection architecture itself, frameworks like AutoFolio achieve speedups ranging from 1.3 to over 15 times compared to using a single default solver, as shown by Lindauer et al. in AutoFolio: An Automatically Configured Algorithm Selector.
Parallel Portfolios as an Alternative
When feature extraction is too expensive or the problem structure is completely opaque, an alternative strategy is to run algorithms concurrently. Petrik et al. explore this in Learning Static Parallel Portfolios of Algorithms, where a collection of solvers runs simultaneously on a single processor. By optimizing the fixed share of CPU time allocated to each solver, parallel portfolios mitigate the risk of a single algorithm getting stuck in an endless search, providing a robust safety net against performance volatility.
Whether through predictive routing or parallel execution, algorithm selection shifts the paradigm from finding the best algorithm to finding the best match, unlocking massive efficiency gains across combinatorial optimization, formal verification, and machine learning.