Automated Algorithm Selection: Survey and Perspectives
  It has long been observed that for practically any computational problem that
has been intensely studied, different instances are best solved using different
algorithms. This is particularly pronounced for computationally hard problems,
where in most cases, no single algorithm defines the state of the art; instead,
there is a set of algorithms with complementary strengths. This performance
complementarity can be exploited in various ways, one of which is based on the
idea of selecting, from a set of given algorithms, for each problem instance to
be solved the one expected to perform best. The task of automatically selecting
an algorithm from a given set is known as the per-instance algorithm selection
problem and has been intensely studied over the past 15 years, leading to major
improvements in the state of the art in solving a growing number of discrete
combinatorial problems, including propositional satisfiability and AI planning.
Per-instance algorithm selection also shows much promise for boosting
performance in solving continuous and mixed discrete/continuous optimisation
problems.
  This survey provides an overview of research in automated algorithm
selection, ranging from early and seminal works to recent and promising
application areas. Different from earlier work, it covers applications to
discrete and continuous problems, and discusses algorithm selection in context
with conceptually related approaches, such as algorithm configuration,
scheduling or portfolio selection. Since informative and cheaply computable
problem instance features provide the basis for effective per-instance
algorithm selection systems, we also provide an overview of such features for
discrete and continuous problems. Finally, we provide perspectives on future
work in the area and discuss a number of open research challenges.
