Algorithm runtime prediction: Methods & evaluation

By Frank Hutter, Lin Xu, Holger H. Hoos, Kevin Leyton-Brown. 2012

454 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Optimal Decision Trees for the Algorithm Selection Problem: Integer Programming Based Approaches (2019, methodology): “These features are similar to the ones used in (Hutter et al., 2014b) with the notable exception that features that are computationally expensive to extract were discarded to ensure that our approach would incur no overhead when incorporated into an algorithm.”
Meta-Learning: A Survey (2018, neutral): “[68] provide a general treatise on predicting algorithm runtime in various domains.”
Algorithm Runtime Prediction: Methods and Evaluation (Extended Abstract) (2015, methodology): “In this invited extended abstract of our AI Journal paper [Hutter et al., 2014b], we summarized existing and new techniques for predicting algorithm runtime and evaluated their performance in a comprehensive empirical analysis.”
Solving Mixed Integer Programs Using Neural Networks (2020, background): “For example, Hutter et al. (2014) shows that it is possible to accurately predict the running time of MIP solvers as a function of the solver parameters and the instance being solved.”
Mondrian Forests for Large-Scale Regression when Uncertainty Matters (2015, methodology): “[14] proposed a further modification, see Appendix C.”
Automated Algorithm Selection: Survey and Perspectives (2018, methodology): “Their set of 287 features builds on the earlier work by Hutter et al. (2014b), but additionally includes instance characteristics derived from the distances of the cities to the convex hull, the number of intersections of locally optimal tours, and statistics of disjoint tour segments.”
Selecting Near-Optimal Learners via Incremental Data Allocation (2015, background): “Note, however, that most selection algorithms use parameterized accuracy models which are ﬁt to data [e.g., 20].”
Performance-influence models for highly configurable systems (2015, background): “There are many successful approaches that aim at finding optimal configurations without pinpointing the influence of configuration options explicitly [7, 12, 13].”
Bayesian Optimization with an Empirical Hardness Model for approximate Nearest Neighbour Search (2014, background): “A recent evaluation of Machine Learning models for performance prediction has shown both Random Forests and GPs to be the best options [8].”
On learning and branching: a survey (2017, background): “(2006) for the former and to Hutter et al. (2014) and Marcos Alvarez et al.”
Taking Human out of Learning Applications: A Survey on Automated Machine Learning (2018, methodology): “algorithm selection optimization algorithms selection of algorithms and their hyper-parameters [38], [50], [51], [52], [53]”
An Efficient Approach for Assessing Hyperparameter Importance (2014, background): “…linear time given a random forest model as input (constructing the random forest is a separate problem, but is also cheap: for T data points of dimensionality n, it is O(n · T 2 log T ) in the worst case and O(n · T log 2 T ) in the more realistic best case of balanced trees (Hutter et al., 2014)).”