Source-linked AI summary
ASlib: A Benchmark Library for Algorithm Selection
Bernd Bischl, Pascal Kerschke, Lars Kotthoff, Marius Lindauer, Yuri Malitsky, Alexandre Frechette, Holger Hoos, Frank Hutter, Kevin Leyton-Brown, Kevin Tierney, Joaquin Vanschoren
TL;DR
Algorithm-selection research lacked a standard format and repository for sharing and comparing per-instance selection approaches. This paper introduces ASlib, a standardized cross-domain scenario library with common evaluation tools, and reports selector improvements across most scenarios, while noting important resource and data-coverage boundaries.
Problem
Algorithm-selection research lacks a standard format and repository, making approaches difficult to share and compare systematically.
Method
ASlib standardizes algorithm-selection scenarios, provides an online repository and automated analyses, and enables common-interface evaluation using precomputed data.
Results
ASlib 2.0 contains 17 scenarios from six areas, and algorithm-selection approaches generally outperform the single best solver, with random regression forests best on 13 of 17 datasets.
Takeaways & Limitations
The library enables researchers to compare algorithm selectors systematically and fairly without replicating systems or collecting raw performance data.
Takeaways & Limitations
ASlib excludes actual instances and algorithm binaries, so it cannot generate new performance data by itself.
Abstract
from arXiv · showhide
The task of algorithm selection involves choosing an algorithm from a set of algorithms on a per-instance basis in order to exploit the varying performance of algorithms over a set of instances. The algorithm selection problem is attracting increasing attention from researchers and practitioners in AI. Years of fruitful applications in a number of domains have resulted in a large amount of data, but the community lacks a standard format or repository for this data. This situation makes it difficult to share and compare different approaches effectively, as is done in other, more established fields. It also unnecessarily hinders new researchers who want to work in this area. To address this problem, we introduce a standardized format for representing algorithm selection scenarios and a repository that contains a growing number of data sets from the literature. Our format has been designed to be able to express a wide variety of different scenarios. Demonstrating the breadth and power of our platform, we describe a set of example experiments that build and evaluate algorithm selection models through a common interface. The results display the potential of algorithm selection to achieve significant performance improvements across a broad range of problems and algorithms.
1. Introduction
Algorithm selection addresses the fact that no single solver performs best across all instances, but existing competitions and benchmarks hinder fair, reproducible evaluation. ASlib introduces standardized specifications, datasets, automated checks, and tools to compare selectors systematically.
- Hard computational problems often admit multiple complementary algorithms, so per-instance selection can outperform reliance on one solver.
- Competition benchmarks emphasize instances difficult for standalone solvers rather than the broad easy-to-hard distributions encountered in practice.
- Changing benchmark sets, inconsistent selector formats, and absent selector-construction code make progress difficult to assess and methods difficult to compare.
- ASlib provides a standardized format and cross-domain benchmark library for evaluating algorithm selection techniques on their own terms.The specification covers varied evaluations, initially includes scenarios from six domains, and is paired with an online repository accepting submissions.
- Automated validation, exploratory analysis, and publicly available R software support reproducible scenario inspection and benchmarking.The system checks submitted datasets and generates overviews using regression, clustering, and classification approaches.
2. Background
Per-instance algorithm selection maps problem instances to algorithms using performance measures and often instance features, typically learned through machine learning. Its methods differ from algorithm configuration, which searches parameter settings, and must account for feature-computation overhead.
- Per-instance algorithm selection finds a mapping from problem instances to algorithms that optimizes expected performance over an instance distribution.
- Instance features characterize inputs and are mapped to algorithm choices with machine learning, but feature computation adds cost to the performance measure.
- Selectors may choose one algorithm, schedule several algorithms, classify directly, predict performance with regression, or partition instances with clustering.
- Feature sources range from simple structural properties to solver probing and meta-features, with richer probing features generally costing more to compute.
- Algorithm configuration optimizes parameter settings in a combinatorial space, whereas algorithm selection chooses among a finite set of algorithms.
- ASlib excludes actual instances and algorithm binaries, so it cannot generate new performance data, unlike AClib, though the two resources can be combined.
3. Summary of Format Specification
ASlib defines a standardized scenario format and repository for fair, convenient algorithm-selector evaluation. Its workflow supports staged feature computation, algorithm decisions, performance assessment, and reuse of precomputed data without rerunning solvers.
- ASlib’s format specification represents algorithm selection scenarios and supports fair, convenient scientific comparison of algorithm selectors.
- The generic workflow computes instance features, potentially in dependent stages, before selecting algorithms or schedules under resource budgets.
- Selectors may repeat algorithm execution and stopping checks while incorporating observations from earlier runs into later decisions.
- The library stores performance data in advance, allowing studies to focus computational time on learning selection models rather than running algorithms.
- Precomputed runtimes can be looked up independently of the hardware used.
- ASlib scenarios have a defined basic structure, with complete specification details provided in accompanying technical documentation and the online platform.
4. Algorithm Selection Scenarios Provided in ASlib Release 2.0
ASlib Release 2.0 provides diverse algorithm-selection scenarios spanning problem domains, solver portfolios, feature sets, and instance collections, with many chosen because algorithm selection has substantial room to improve over the single best solver.
- Release 2.0 assembles scenarios covering diverse problem domains, algorithm types, instance features, and problem instances.
- The library includes established SAT and CSP scenarios alongside newer applications such as container pre-marshalling.
- Most scenarios were selected from studies reporting algorithm-selection improvements and have a virtual best solver substantially better than the single best solver.The virtual best solver selects the best solver per instance, whereas the single best solver performs best on average across instances.
- SAT: Propositional Satisfiability: The SAT scenarios combine mature, diverse solver sets with static and probing features organized into as many as ten feature groups.
- CSP: Constraint solving: The CSP scenarios vary from the two-solver CSP-2010 setting to larger MiniZinc-based collections and the diverse PROTEUS scenario combining CSP and SAT solvers.PROTEUS also represents CSP instances through multiple SAT conversions and includes both SAT and CSP features.
5. Automated Exploratory Data Analysis
ASlib automatically generates exploratory summaries of algorithm-selection scenarios, combining performance, feature, correlation, and benchmark analyses. These views expose portfolio redundancy, feature-computation risks, and scenario properties relevant to model development and data checking.
- Automated overviews: The platform generates scenario overviews with summary tables, visualizations, and benchmark results for standard machine-learning models.These outputs cover algorithm performance and run status, feature values and feature-group costs, and per-scenario benchmark results.
- Benefits: Researchers can use the generated summaries to select suitable scenarios, sanity-check data, and obtain an informative first impression of dataset properties.The platform is intended to make available scenarios and potential data-collection errors easier to assess.
- Performance distributions: Performance distributions reveal differences in algorithm speed and coverage, such as quantor solving about 5% of QBF-2011 instances within one second but fewer than 30% overall, while sSolve is slower yet among the best once successful.The plots use boxplots and cumulative distribution functions to summarize runtime distributions and solved-instance percentages.
- Algorithm comparisons: Pairwise scatterplots compare algorithms across instances, indicating when one is usually dominant and when varying relative performance leaves potential for per-instance selection.A dominant algorithm may justify discarding the other from the portfolio, whereas non-dominance indicates possible selection gains.
- Correlation analysis: Correlation matrices identify redundancy and complementarity: highly positively correlated algorithms are more likely redundant, whereas negatively correlated pairs may complement each other.The platform computes Spearman rank correlations and clusters algorithms with similar performance.
- Correlation analysis: SAT12-ALL correlations reveal four highly correlated algorithm groups, suggesting that the portfolio could be reduced from 31 algorithms to four representatives.The groups are minisatpsm–restartsat, sattimep–tnm, marchrw, and the three mphaseSAT algorithms.
- Feature analysis: Feature summaries expose computational risks: the SAT12-RAND CG feature group failed in 37.37% of cases and cost 8.79 seconds on average when successful.CG computes clause-graph features and failed because of time or memory limits.
- Access and extensibility: The platform and aslib provide configurable generated tables and figures, with planned extensions including additional measures of algorithm performance.The same analyses are accessible through the R package aslib.
6. Study of Algorithm Selection Techniques
The study benchmarks several algorithm-selection approaches across ASlib scenarios using common machine-learning methods and comparisons against single-best and virtual-best solvers. Performance varies substantially by scenario, with random regression forests strongest overall and feature and solver subset selection often reducing the necessary inputs.
- Experimental setup: The study evaluates classification, regression, and clustering approaches for algorithm selection across ASlib scenarios.Classification predicts the best algorithm, regression predicts each algorithm’s performance, and clustering assigns algorithms through instance groups.
- Experimental setup: Performance is compared with the virtual best solver and the single best solver, accounting for the best per-instance and overall solver baselines.The virtual best solver chooses the best solver for each instance, while the single best solver has the best overall dataset performance.
- Results: In most cases, algorithm-selection approaches outperform the single best solver, but performance differs substantially across scenarios.On SAT12-INDU, three approaches failed to achieve a performance improvement.
- Results: Random regression forests achieve the best performance on 13 of 17 datasets, making them the strongest overall approach in the study.This result is consistent with prior findings on algorithm runtime prediction and with the original dataset papers.
- Results: XMeans performs worst on average and can perform worse than the single best solver on several industrial SAT scenarios.Its default feature subset appears unfavorable for XMeans on SAT12-ALL, SAT12-INDU, and SAT15-INDU.
- Algorithm and feature subset selection: Forward selection usually reduces the number of features and algorithms while retaining comparable performance, highlighting the value of compact scenario-specific subsets.The study reports that selected feature sets are usually small and that solver subsets are substantially reduced on most scenarios.
7. Competitions on ASlib
ASlib supports ongoing and challenge-based competitions for fair comparison of algorithm selectors. These settings improve accessibility and recency, but differ in resource control and exposure to overfitting.
- Competition settings: ASlib competitions are designed to enable easy and fair comparison of algorithm-selection approaches.The proposed settings evaluate selectors on ASlib scenarios rather than forcing them into competitions designed for standalone solvers.
- Ongoing evaluation: In the ongoing evaluation, participants submit scenario performance and selector source code using provided cross-validation splits.Submitted results are added to an overview table, and source code is used to verify results when necessary.
- Ongoing evaluation: The ongoing evaluation can incorporate new systems and results without submission deadlines, keeping its overview current.Any system able to read the ASlib format can participate, and results can be added on the fly.
- Limitations: Different participants may use substantially different computational resources, complicating direct performance comparisons.SATzilla and AutoFolio are cited as well-performing systems using several CPU days, more than some other systems.
- Limitations: Published training and test data can encourage overfitting unless new scenarios are regularly introduced.The paper identifies regular provision of new scenarios as a way to reveal such overfitting.
- ICON Challenge: The ICON Challenge compared algorithm selectors using solved instances, PAR10, and misclassification penalty, revealing metric-dependent strengths and weaknesses.Systems using algorithm schedules performed better on solved instances and PAR10 but wasted time with respect to MCP.
8. Summary
ASlib provides a common benchmark library and tools for principled empirical comparison of algorithm-selection methods. Its second release spans 17 scenarios across six areas and includes automated exploratory analysis and benchmark experiments.
- Contributions: ASlib provides common benchmarks and tools that facilitate algorithm-selection research and principled comparative empirical performance assessment.The library also lowers the barrier for researchers working on algorithm selection.
- Release 2.0: Release 2.0 contains 17 algorithm-selection scenarios from six areas, with a focus on but not limitation to constraint satisfaction problems.The scenarios were selected to challenge algorithm-selection methods in varied ways.
- Platform: ASlib’s online platform automatically performs exploratory data analysis for newly submitted scenarios.The paper describes automated overviews and examples of benchmark results generated for submitted data.
- Empirical studies: Exploratory studies demonstrate the performance that algorithm-selection systems can achieve on the included scenarios.These studies use various algorithm-selection approaches to assess the library’s scenarios.