Algorithm Runtime Prediction: Methods and Evaluation (Extended Abstract)

1 Introduction

NP-complete problems are ubiquitous in AI. Luckily, while these problems may be hard to solve on worst-case inputs, it is often feasible to solve even large problem instances that arise in practice. Less luckily, state-of-the-art algorithms often exhibit extreme runtime variation across instances from realistic distributions, even when problem size is held constant, and conversely the same instance can take dramatically different amounts of time to solve depending on the algorithm used [Gomes et al., 2000]. There is little theoretical understanding of what causes this variation. Over the past decade, a considerable body of work has shown how to use supervised machine learning methods to build regression models that provide approximate answers to this question based on given algorithm performance data. We refer to such models as empirical performance models (EPMs). These models are useful in a variety of practical contexts:

• Algorithm selection. This classic problem of selecting the best from a given set of algorithms on a per-instance

∗This paper is an invited extended abstract of our 2014 AI Journal article [Hutter et al., 2014b]

basis [Rice, 1976; Smith-Miles, 2009; Kotthoff, 2014] has been successfully addressed by using EPMs to predict the performance of all candidate algorithms and selecting the one predicted to perform best [Brewer, 1995; Lobjois and Lemaˆıtre, 1998; Fink, 1998; Howe et al., 2000; Nudelman et al., 2003; Roberts and Howe, 2007; Xu et al., 2008; Kotthoff et al., 2012].

• Parameter tuning and algorithm configuration. EPMs are useful for these problems in at least two ways. First, they can model the performance of a parameterized algorithm dependent on the settings of its parameters; in a sequential model-based optimization process, one alternates between learning an EPM and using it to identify promising settings to evaluate next [Jones et al., 1998; Bartz-Beielstein et al., 2005; Hutter et al., 2011]. Second, EPMs can model algorithm performance dependent on both problem instance features and algorithm parameter settings; such models can then be used to select parameter settings with good predicted performance on a per-instance basis [Hutter et al., 2006].
• Generating hard benchmarks. An EPM for one or more algorithms can be used to set the parameters of existing benchmark generators in order to create instances that are hard for the algorithms in question [Leyton-Brown et al., 2009].
• Gaining insights into instance hardness and algorithm performance. EPMs can be used to assess which instance features and algorithm parameter values most impact empirical performance. Some models support such assessments directly [Ridge and Kudenko, 2007; Mersmann et al., 2013; Hutter et al., 2014a]. For other models, generic feature selection methods, such as forward selection, can be used to identify a small number of key model inputs (often fewer than five) that explain algorithm performance almost as well as the whole set of inputs [Leyton-Brown et al., 2009; Hutter et al., 2013].

While these applications motivate our work, we do not discuss them in detail in our article; instead, we focus on the models themselves. The idea of modeling algorithm runtime is no longer new; however, we have made substantial recent progress in making runtime prediction methods more general, scalable and accurate. After a comprehensive review of past work on runtime prediction from many separate communities, our AI Journal article [Hutter et al., 2014b] makes four new contributions:

1. We describe new, more sophisticated modeling techniques (based on random forests and approximate Gaussian processes) and methods for modeling runtime variation arising from the settings of a large number of (both categorical and continuous) algorithm parameters.
2. We introduce new instance features for propositional satisfiability (SAT), travelling salesperson (TSP) and mixed integer programming (MIP) problems-in particular, novel probing features and timing features-yielding comprehensive sets of 138, 121, and 64 features for SAT, MIP, and TSP, respectively.
3. To assess the impact of these advances and to determine the current state of the art, we performed what we believe is the most comprehensive evaluation of runtime prediction methods to date. Specifically, we evaluated all methods of which we are aware on performance data for 11 algorithms and 35 instance distributions spanning SAT, TSP and MIP and considering three different problems: predicting runtime on novel instances, novel parameter configurations, and both novel instances and configurations.
4. Techniques from the statistical literature on survival analysis offer ways to better handle data from runs that were terminated prematurely. While these techniques were not used in most previous work-leading us to omit them from our broad empirical evaluation-we show how to leverage them to achieve further improvements to our best-performing model, random forests.

In this extended abstract of our AI Journal article, we provide a high-level description of the modeling techniques (Section 3) and instance features (Section 4) and give some exemplary empirical results (Section 5).

2 ProblemDefinition

We describe a problem instance by a list of m features z = [z1, . . . , zm]T , drawn from a given feature space F. These features must be computable by a piece of problemspecific code (usually provided by a domain expert) that efficiently extracts characteristics for any given problem instance (typically, in low-order polynomial time w.r.t. the size of the given problem instance). We define the configuration space of a parameterized algorithm with k parameters θ1, . . . , θk with respective domains Θ1, . . . , Θk as a subset of the crossproduct of parameter domains: Θ ⊆ Θ1 × · · · × Θk. The elements of Θ are complete instantiations of the algorithm's k parameters, and we refer to them as configurations. We note that parameters can be numerical (continuous- or realvalued) or categorical (with finite unordered domain, as, e.g., for parameters that govern which of several heuristics to use).

Given an algorithm A with configuration space Θ and a distribution of instances with feature space F, an EPM is a stochastic process that defines a probability distribution over performance measures for each combination of a parameter configuration θ ∈ Θ of A and a problem instance with features z ∈ F. The prediction of an entire distribution allows us to assess the model's confidence at a particular input. While this is essential in some applications (e.g., in model-based algorithm configuration), many previous models do not quantify uncertainty. We thus chiefly evaluate our models in terms of their mean predictions.

3 Modeling Techniques

We evaluated the following algorithm runtime prediction methods from previous work:

• RR: ridge regression with quadratic basis function expansion and forward selection as in early versions of SATzilla [Leyton-Brown et al., 2009; Xu et al., 2008]);
• SP: SPORE-FoBa, a variant of RR that performs forwardbackward feature selection [Huang et al., 2010];
• NN: neural networks (as used by Smith-Miles and van Hemert [2011]); and
• RT: regression trees (as used by Bartz-Beielstein and Markon [2004]).

Out of these models, only regression trees natively handle categorical inputs. In order to apply the other model types to construct EPMs for algorithms with categorical parameters, we used a 1-in-K encoding (also known as 1-hot encoding). We also used two methods newly in the context of runtime prediction:

• GP: approximate Gaussian processes [Rasmussen and Williams, 2006], equipped with a new kernel for categorical parameters; and
• RF: random forests [Breiman, 2001], adapted with a new method to quantify predictive uncertainties and a new method for choosing split points to yield linear interpolations (and uncertainty estimates that grow with distance to observed data points) in the limit of an infinite number of trees.

4 Features

Instance features are inexpensively computable, problemdependent characteristics that distinguish instances from one another. In our AI Journal paper we describe a large set of 138, 121, and 64 features for SAT, MIP, and TSP, respectively. In particular, we review many existing features and also introduce various new features, including the following two general classes:

• Probing features: we execute a cheap algorithm for the actual problem instance and keep track of several statistics; e.g., counting the number of clauses a DPLL SAT solver learns in 2 seconds;
• Timing features: we measure the time the computation of various features take; this timing information can be a very useful feature in itself.

5 Empirical Results

We now summarize some results that are representative of our findings about runtime prediction on (a) new instances and (b) new instances and configurations.

5.1 Predictions for New Instances

Table 1 provides quantitative results for all benchmarks, and Figure 1 visualizes some results in more detail. At the broadest level, we can conclude that most of the methods were able to capture enough information about algorithm performance on training data to make meaningful predictions on test data, most of the time: easy instances tended to be predicted as being easy, and hard ones as being hard. Take, for example the case of predicting the runtime of Minisat 2.0 on a heterogeneous mix of SAT competition instances (see the leftmost column in Figure 1 and the top row of Table 1). Minisat 2.0 runtimes varied by almost six orders of magnitude, while predictions made by the better models were rarely off by more than one order of magnitude (outliers may draw the eye in the scatterplot, but quantitatively, the RMSE for predicting log10 runtime was low-e.g., 0.47 for random forests, which means an average misprediction of a factor of 100.47 < 3). While the models were certainly not perfect, note that even the relatively poor predictions of ridge regression tended to be accurate within about an order of magnitude, which was sufficient to enable the portfolio-based algorithm selector SATzilla [Xu et al., 2008] to win five medals in each of the 2007 and 2009 SAT competitions.

In our experiments, random forests were the overall winner among the different methods, yielding the best predictions in terms of all our quantitative measures.We attribute their strong performance on highly heterogeneous data sets to the fact that, as a tree-based approach, they can model very different parts of the data separately; in contrast, the other methods allow the fit in a given part of the space to be influenced more by data in distant parts of the space. Indeed, the ridge regression variants made extremely bad predictions for some outlying points on CPLEX-BIGMIX. For the more homogeneous MIP data sets, either random forests or projected processes performed best, often followed closely by ridge regression. In terms of computational requirements, random forests were also among the cheapest methods, taking between 0.1 and 11 seconds to learn a model.

5.2 Predictions for New Instances and New Configurations

We now examine the most interesting case, where test instances and algorithm parameter configurations were both previously unseen. Table 2 provides quantitative results of model performance based on n = 10 000 training data points, and Figure 2 visualizes performance. Overall, we note that the best models generalized to new configurations and to new instances almost as well as to either alone. On the most heterogeneous data set, CPLEX-BIGMIX, we once again witnessed extremely poorly predicted outliers for the ridge regression variants, but in all other cases, the models captured the large spread in runtimes (above 5 orders of magnitude) quite well. As in the experiments in Section 5.1, the tree-based approaches, which model different regions of the input space independently, performed best on the most heterogeneous data sets. Figure 2 also shows some qualitative differences in predictions: for example, ridge regression, neural networks, and projected processes sometimes overpredicted the runtime of the shortest runs, while the tree-based methods did not have this problem. Random forests performed best in all cases.

Finally, Figure 3 qualitatively compares true runtimes to those predicted by random forests and ridge regression using the heterogeneous data set SPEAR-SWV-IBM. We note that the true heatmaps are very similar to those predicted by random forests, while the non-tree-based methods (here: ridge regression) only captured instance hardness, failing to distinguish good from bad configurations (even in the simplest case of predictions for training instances and training configurations).

6 Conclusion

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. Particularly noteworthy is the rather good predictability of runtime for new problem instances and new configurations of parameterized algorithms. We encourage the interested reader to consult our full journal article for a complete account of our methods and findings. Overall, in this article, we show that the performance prediction methods we studied are fast, general, and achieve good, robust performance. We hope they will be useful to a wide variety of researchers who seek to model algorithm performance for algorithm analysis, scheduling, algorithm portfolio construction, automated algorithm configuration, and other applications. The Matlab source code for our models, the data and source code to reproduce our experiments, and an online appendix containing additional experimental results, are available at http://www.cs.ubc.ca/labs/beta/Projects/EPMs.