Algorithm selection

Algorithm selection chooses an algorithm for a particular problem instance using information available before or during its solution. The available candidates form an algorithm portfolio. John R. Rice's 1976 treatment formalized the relationship between problem descriptions, descriptive features, algorithms and performance criteria.^[ref]

An original runtime example shows the potential benefit. Suppose algorithms $A$ and $B$ take $(2,20)$ and $(10,3)$ seconds on two equally likely instance types. Always choosing $A$ gives mean $11$ seconds; always choosing $B$ gives $6.5$ seconds. A selector that reliably recognizes both types and chooses the faster algorithm gives mean $2.5$ seconds before selection overhead. If computing its features and choosing costs another second, the total becomes $3.5$ seconds. The gain comes from complementary performance, not from either candidate being universally faster.

The hypothetical $2.5$-second result assumes perfect decisions. A real selector can misclassify instances, spend time extracting features or encounter inputs unlike its training examples. Its complete measured runtime includes those costs. Looking up the faster solver after both have finished supplies a useful comparison bound, but does not itself implement an online choice.

Algorithm configuration instead searches settings of a parameterized target algorithm. The two ideas can be combined by selecting among configured candidates, provided the evaluation states what was tuned, what was selected and which instances were reserved for testing.