algsel

AlgSel, short for algorithm selection, refers to the problem of choosing the most appropriate algorithm for each problem instance from a predefined portfolio. The concept is central to the broader field of automated solver design and originated in the algorithm selection literature during the 1970s, notably with J. H. Rice's formulation The Algorithm-Selection Problem. The aim is to maximize performance, typically measured in runtime, accuracy, or solution quality, on a distribution of instances.

In standard models, an instance I is described by a feature vector x(I) computed from instance properties. A set of algorithms A is available, each with observed performance p(a, I). The goal is to learn a selection function s that maps features to an algorithm, s(x) = a, such that the expected performance of a is optimized over the training distribution. Methods include per-instance prediction using machine learning (classification, regression, ranking), portfolio approaches that combine multiple algorithms, and dynamic or anytime strategies that switch algorithms during solving.

AlgSel has been applied across domains such as SAT, constraint satisfaction, AI planning, and optimization. Practical work emphasizes informative, inexpensive features, reliable performance data, and robust generalization to unseen instances. Public benchmarks and datasets, such as the Algorithm Selection Library (ASLib), provide standardized data to train and evaluate selection models and to compare different approaches.

While algsel can yield substantial performance gains by exploiting instance heterogeneity, challenges remain. These include the cost of feature extraction, model maintenance for evolving problem distributions, and ensuring that portfolios remain effective across diverse workloads.