Algorithm Runtime Prediction: Methods & Evaluation
  Perhaps surprisingly, it is possible to predict how long an algorithm will
take to run on a previously unseen input, using machine learning techniques to
build a model of the algorithm's runtime as a function of problem-specific
instance features. Such models have important applications to algorithm
analysis, portfolio-based algorithm selection, and the automatic configuration
of parameterized algorithms. Over the past decade, a wide variety of techniques
have been studied for building such models. Here, we describe extensions and
improvements of existing models, new families of models, and -- perhaps most
importantly -- a much more thorough treatment of algorithm parameters as model
inputs. We also comprehensively describe new and existing features for
predicting algorithm runtime for propositional satisfiability (SAT), travelling
salesperson (TSP) and mixed integer programming (MIP) problems. We evaluate
these innovations through the largest empirical analysis of its kind, comparing
to a wide range of runtime modelling techniques from the literature. Our
experiments consider 11 algorithms and 35 instance distributions; they also
span a very wide range of SAT, MIP, and TSP instances, with the least
structured having been generated uniformly at random and the most structured
having emerged from real industrial applications. Overall, we demonstrate that
our new models yield substantially better runtime predictions than previous
approaches in terms of their generalization to new problem instances, to new
algorithms from a parameterized space, and to both simultaneously.
