On Algorithm Selection, with an Application to Combinatorial Search Problems

The Algorithm Selection Problem is to select the most appropriate way for
solving a problem given a choice of different ways. Some of the most prominent
and successful applications come from Artificial Intelligence and in particular
combinatorial search problems. Machine Learning has established itself as the de
facto way of tackling the Algorithm Selection Problem. Yet even after a decade
of intensive research, there are no established guidelines as to what kind of
Machine Learning to use
and how.

This dissertation presents an overview of the field of Algorithm Selection and
associated research and highlights the fundamental questions left open and
problems facing practitioners. In a series of case studies, it underlines the
difficulty of doing Algorithm Selection in practice and tackles issues related
to this. The case studies apply Algorithm Selection techniques to new problem
domains and show how to achieve significant performance improvements. Lazy
learning in constraint solving and the implementation of the
\texttt{alldifferent} constraint are the areas in which we improve on the
performance of current state of the art systems. The case studies furthermore
provide empirical evidence for the effectiveness of using the misclassification
penalty as an input to Machine Learning.

After having established the difficulty, we present an effective technique for
reducing it. Machine Learning ensembles are a way of reducing the background
knowledge and experimentation required from the researcher while increasing the
robustness of the system. Ensembles do not only decrease the difficulty, but can
also increase the performance of Algorithm Selection systems. They are used to
much the same ends in Machine Learning itself.

We finally tackle one of the great remaining challenges of Algorithm Selection
-- which Machine Learning technique to use in practice. Through a large-scale
empirical evaluation on diverse data taken from Algorithm Selection applications
in the literature, we establish recommendations for Machine Learning algorithms
that are likely to perform well in Algorithm Selection for combinatorial search
problems. The recommendations are based on strong empirical evidence and
additional statistical simulations.

The research presented in this dissertation significantly reduces the knowledge
threshold for researchers who want to perform Algorithm Selection in practice.
It makes major contributions to the field of Algorithm Selection by
investigating fundamental issues that have been largely ignored by the research
community so far.