PaperlayerView exact revision on arXiv

Source-linked AI summary

Algorithm Runtime Prediction: Methods & Evaluation

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

arXiv:1211.0906v2cs.AIcs.LGcs.PFstat.ML

TL;DR

Predicting runtimes for hard combinatorial algorithms requires models that handle instance variation and algorithm parameters. This paper advances runtime modeling with new techniques and features, and evaluates them broadly, finding improved predictions across new instances, algorithms, and both simultaneously.

  • Problem

    Runtime prediction must account for extreme variation across realistic instances and is limited when direct modeling methods handle only small numbers of continuous algorithm parameters.

  • Method

    The paper develops random-forest and approximate-Gaussian-process models, treats categorical and continuous algorithm parameters as inputs, and introduces SAT, MIP, and TSP instance features.

  • Results

    The new approaches yielded substantially better runtime predictions than previous methods when generalizing to new instances, new parameterized algorithms, and both simultaneously.

  • Takeaways & Limitations

    Runtime models can support algorithm analysis, portfolio-based algorithm selection, and automatic configuration of parameterized algorithms.

  • Takeaways & Limitations

    The empirical evaluation required between 604,000 and 2,000,000 runs per instance distribution and over 60 CPU years of computation.

Abstract

from arXiv · show

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.

1. Introduction

Algorithm runtimes vary dramatically across realistic instances and algorithm choices, motivating empirical performance models (EPMs). The paper advances runtime modeling with new techniques, features, and a broad evaluation across algorithms, problems, instances, and parameter configurations.

  • Runtime can vary dramatically across realistic instances, even when problem size is fixed, and the same instance can take different times under different algorithms.
  • EPMs use supervised machine learning to approximate algorithm performance from observed performance data.The paper uses EPM as an umbrella term that includes empirical hardness models.
  • EPMs support algorithm selection, parameter tuning and configuration, hard-benchmark generation, and analysis of instance hardness and algorithm performance.
  • The work focuses on making runtime prediction methods more general, scalable, and accurate rather than detailing their applications.
  • The paper introduces more sophisticated models, parameter-aware modeling methods, and new SAT, TSP, and MIP instance features.The feature sets contain 138 SAT, 121 MIP, and 64 TSP features.
  • The evaluation compares runtime prediction methods on 11 algorithms and 35 instance distributions, covering novel instances, novel parameter configurations, and both simultaneously.

2. An Overview of Related Work

Prior work developed runtime prediction across several communities, but parameterized-algorithm modeling remained limited in handling many and categorical parameters. Response surface models address prediction at unobserved parameter settings, while runtime prediction must also account for instance variation and censored runs.

  • 2.1. Related Work on Predicting Runtime of Parameterless Algorithms: Runtime prediction research grew from parallel computing, AI planning, constraint programming, and combinatorial-problem studies beginning at least in the mid-1990s.
  • 2.1. Related Work on Predicting Runtime of Parameterless Algorithms: Earlier runtime models used regression and other methods to predict performance across algorithms and instance distributions.
  • 2.1. Related Work on Predicting Runtime of Parameterless Algorithms: Capped runs provide only lower bounds on runtime, making right-censoring an important modeling issue for runtime prediction.
  • 2.2. Related Work on Predicting Runtime of Parameterized Algorithms: Directly treating algorithm parameters as model inputs is effective mainly for small numbers of continuous-valued parameters.
  • 2.2. Related Work on Predicting Runtime of Parameterized Algorithms: Response surface models predict process outputs at unobserved settings of controllable input parameters and underpin sequential model-based optimization.
  • 2.2. Related Work on Predicting Runtime of Parameterized Algorithms: Most algorithm-performance response surface literature considered single instances and continuous parameters, with limited work relaxing those assumptions.
  • 2.2. Related Work on Predicting Runtime of Parameterized Algorithms: Mixed-effects approaches treat instance characteristics as random effects and assume Gaussian performance distributions, an assumption noted as less realistic for runtime prediction.

3. Methods Used in Related Work

The paper frames EPMs as stochastic predictors over instance features and algorithm configurations, then reviews regression, neural, Gaussian-process, and tree-based methods. Modeling choices include transformations, feature selection, regularization, and scalable approximations.

  • 3. Methods Used in Related Work: The methods reviewed include ridge regression, neural networks, Gaussian process regression, and regression trees.
  • 3.1. Preliminaries: Parameterized-algorithm inputs combine configuration parameters and instance features in the joint input space I = Θ × F.
  • 3.1. Preliminaries: An EPM maps each combination of an algorithm configuration and problem-instance features to a probability distribution over performance measures.
  • 3.1. Preliminaries: Training data records algorithm performance for configuration-instance combinations, using predictor vectors that concatenate parameters and instance features.
  • 3.1. Preliminaries: Runtime is log-transformed because hard combinatorial problems exhibit large runtime variation, while missing feature values are normalized and set to zero for training.
  • 3.2. Ridge Regression: Ridge regression fits a linear function and regularizes coefficients, improving numerical stability when inputs are rank deficient or nearly so.
  • 3.2. Ridge Regression: Quadratic basis expansions add pairwise products of inputs to represent potentially nonlinear runtime relationships.
  • 3.2. Ridge Regression: Forward selection greedily chooses inputs by cross-validation error, then performs a quadratic expansion of the selected features.

3.4. Gaussian Process Regression

Gaussian process regression models similarity through a kernel, combines this prior with observed training data, and produces a posterior prediction for new inputs. Regression trees instead partition the input space recursively and predict a leaf-specific constant.

  • Gaussian process regression: Gaussian processes use a kernel to characterize similarity between input pairs and define a prior distribution over functions.For continuous inputs, the standard choice is the squared exponential kernel, whose correlations decrease with weighted Euclidean distance.
  • Gaussian process regression: Training data and the kernel prior yield a posterior distribution at a new input, with hyperparameters optimized by maximizing the data’s marginal likelihood.The hyperparameters include kernel parameters and observation-noise variance.
  • Gaussian process regression: Exact Gaussian-process fitting costs O(h·n^3), while predictions require O(n) for the mean and O(n^2) for the variance.The cubic fitting cost arises from repeatedly inverting an n × n matrix during hyperparameter optimization.
  • Regression trees: Regression trees partition the input space into disjoint regions and predict a constant sample mean within the selected leaf.The error-minimizing constant under squared error is the sample mean of training points in that region.
  • Regression trees: Trees recursively choose binary splits that minimize the sum of squared deviations from the means of the resulting regions, then prune branches to mitigate overfitting.Splits support both real-valued and categorical variables.
  • Regression trees: Regression-tree prediction follows a new input down the tree and returns the selected leaf’s constant, with no variance predictor.Prediction costs O(n) in the worst case and O(log n) for a balanced tree.

4. New Modeling Techniques for EPMs

The paper extends empirical performance models for highly parameterized algorithms with categorical-input handling, new model families, scalable Gaussian-process approximations, and uncertainty estimates for random forests. It also introduces a direct categorical kernel and comprehensive problem features for SAT, MIP, and TSP.

  • Section 4 overview: The proposed extensions target runtime prediction for highly parameterized algorithms and include categorical inputs, projected-process Gaussian processes, and random forests.The methods are designed for partially categorical configuration spaces and potentially large datasets.
  • Categorical inputs: 1-in-K encoding replaces each categorical input with binary indicator columns, but can considerably enlarge the input space.Each data point has exactly one active indicator for a categorical dimension.
  • Categorical inputs: The new mixed kernel handles categorical inputs directly by replacing weighted squared distance with weighted Hamming distance.It combines continuous and categorical dimensions and is shown to be positive definite.
  • Projected-process Gaussian processes: Projected-process Gaussian processes reduce fitting complexity to O([h · a + n] · a^2), compared with O(h · n^3) for exact Gaussian processes.The approximation uses an active set of a training points, with a ≪ n yielding faster fitting.
  • Random forests: Random forests reduce regression-tree variance by aggregating multiple trees trained with random subsets of variables at each split.The implementation uses the full training set for each tree and does not prune the trees.
  • Random forests: The paper adds random-forest uncertainty estimates by storing empirical leaf variances and imposing a minimum variance of σ^2_min = 0.01.Each tree contributes a predictive mean and variance that are combined across the forest.

5. Problem-Specific Instance Features

The paper develops comprehensive, problem-specific feature sets for SAT, MIP, and TSP, combining established descriptors with novel probing and timing features. These features are organized by computational cost so users can trade predictive information against feature-extraction overhead.

  • All features are polynomial-time computable, but some are expensive; four cost classes support selecting subsets for runtime-sensitive applications.For repeated model building, the paper notes that even feature costs exceeding instance-solving time can be reasonable.
  • Probing features briefly run an existing solver and extract characteristics from its search trajectory; new probing sets are introduced for MIP and TSP.Earlier SAT work found that probing one algorithm type could help predict another type’s performance.
  • SAT: Feature sets include novel SAT graph features, clause-learning and survey-propagation features, plus timing measurements for feature-computation blocks.SAT’s new graph features include variable-graph diameter and clause-graph clustering coefficients.
  • MIP: MIP features comprise existing problem, graph, matrix, objective, and LP descriptors alongside 15 probing features and 5 timing features.The new MIP probing features are based on 5-second CPLEX runs with default settings.
  • TSP: TSP features cover problem size, costs, minimum spanning trees, clusters, local search, branch-and-cut probing, search ruggedness, and feature-computation timing.Local-search probing uses 20 short LK runs, while branch-and-cut probing uses 2-second Concorde runs.

6. Performance Predictions for New Instances

The study evaluates runtime prediction on unseen instances across SAT, MIP, and TSP benchmarks, finding that most models capture substantial runtime variation. Random forests perform best overall, while feature cost and hyperparameter optimization involve practical trade-offs.

  • Predictive Quality: Most models made meaningful predictions on unseen instances, usually distinguishing easy from hard cases.For Minisat 2.0 on heterogeneous SAT competition instances, runtimes spanned almost six orders of magnitude, while better predictions were rarely off by more than one order.
  • Predictive Quality: 0.47 RMSE for random forests on log10 runtime corresponded to an average misprediction factor below 3.
  • Predictive Quality: Random forests were the overall winner across quantitative measures, always best for SAT and strongest on heterogeneous MIP data.Tree-based models can fit different regions of heterogeneous data independently; projected processes or ridge regression were often competitive on more homogeneous MIP sets.
  • Feature Classes: Using more computationally expensive features generally improved prediction, but moderately expensive features matched the best results on all SAT benchmarks without equivalent computation cost.The new cheap feature set also achieved performance similar to previous features at lower cost.
  • Hyperparameter Optimization: Hyperparameter optimization improved models slightly and reduced some ridge-regression outliers, but made training dramatically slower.The authors therefore used fixed default hyperparameters for subsequent evaluation because the small accuracy gains were unlikely to justify the computational cost.
  • Training-Data Scaling: Random forests performed best across training-set sizes, whereas both ridge-regression variants performed poorly with small training sets.This matters because earlier work often evaluated ridge regression only with large amounts of data.

7. Performance Predictions for New Parameter Configurations

The paper extends runtime prediction from unseen instances to unseen parameter configurations, evaluating models on highly parameterized SAT and MIP solvers. Projected processes lead overall, with random forests consistently close behind and more robust than several alternatives.

  • Evaluation Settings: The evaluation considers four generalization settings combining training or test instances with training or test configurations.The section focuses on predicting performance across parameterized solver families, including cases relevant to algorithm selection and configuration.
  • Experimental Setup: The experiments trained models from 1 000 randomly sampled configurations for SPEAR and CPLEX on selected SAT and MIP distributions.
  • Algorithms and Configuration Spaces: SPEAR uses 26 parameters, while CPLEX uses a 76-parameter configuration space.SPEAR’s discretized space contains 8.34 × 10^17 configurations, illustrating the scale of the parameterized setting.
  • Predictive Quality: Most methods predicted runtime over parameter settings well despite runtime variation exceeding a factor of 1 000.
  • Predictive Quality: Projected processes achieved the best overall performance, while random forests were either best or very close to best on every data set.Projected processes, random forests, and ridge regression variant RR consistently outperformed regression trees.
  • Training-Data Scaling: Projected processes remained best overall as training configurations varied, followed closely by random forests.RR improved with sufficient data, whereas SPORE-FoBa and neural networks remained relatively poor regardless of training-set size.

8. Performance Predictions in the Joint Space of Instance Features and Parameter Configurations

The joint-space experiments test whether runtime models generalize simultaneously to unseen instances and configurations. Random forests perform best, often requiring only a few hundred training points for strong correlations, although heterogeneous benchmarks need more data.

  • Experimental Setup: The joint-space evaluation splits both instances and configurations into equal training and test sets, then trains models on sampled instance–configuration combinations.The experiments use 1 000 configurations and between 604 and 2 000 problem instances per distribution.
  • Experimental Setup: The evaluation required between 604 000 and 2 000 000 runs per distribution and over 60 CPU years, although practical use requires far less experimentation.
  • Joint Generalization: Random forests performed best when both instances and configurations were unseen, capturing runtime spreads above 5 orders of magnitude in most cases.Tree-based approaches were strongest on heterogeneous data, while ridge regression produced severe outliers on CPLEX-BIGMIX.
  • Sparse Training Data: Correlation coefficients of 0.9 and higher were achieved by most models with a few hundred training data points.Random forests performed best across training sizes; heterogeneous benchmarks such as CPLEX-BIGMIX required more data than homogeneous CPLEX-CORLAT.
  • Four Train/Test Combinations: For SPEAR-SWV-IBM, predicted runtime heatmaps from random forests were almost indistinguishable from the true heatmaps across all four train/test combinations.
  • Training-Data Scaling: With 100 training points, random forests captured salient easy-instance structure, while additional data yielded diminishing returns.Using 10 000 samples produced predictions not much different from using the full 151 000–500 000-point training cross-product.

9. Improved Handling of Censored Runtimes in Random Forests

The section formalizes runtime censoring and compares four ways to model capped runs with random forests. Instance-specific captimes improve predictions for larger runtimes, while the modified Schmee–Hahn approach preserves uncertainty and achieves strong accuracy under varying thresholds.

  • Censored runtimes: A capped run yields a right-censored observation: the captime κ is known as a lower bound on the unknown runtime.The training data records input features, an observed runtime, and a censoring indicator distinguishing exact from lower-bound observations.
  • Censored runtimes: Treating censored runs as finishing at κ biases training data downward and predictions accordingly.Survival-analysis methods provide a principled alternative for regression with censored observations.
  • Random-forest methods: Schmee–Hahn modeling uses expectation maximization, alternating imputation for censored runs with refitting the random forest.The modified procedure samples predictive distributions per tree rather than assigning identical imputed values, retaining uncertainty across trees.
  • Experimental comparison: With a fixed threshold, dropping censored data underestimates runtimes, κ-imputation works only up to κ, and Schmee–Hahn variants remain unbiased to about 2κ.The comparison includes dropping censored points, treating them as uncensored at κ, and both Schmee–Hahn variants.
  • Experimental comparison: With varying captimes, the Schmee–Hahn variants—especially the new one—produce the lowest prediction error and competitive uncertainty estimates.These findings remain robust to how aggressively captimes are chosen; instance-specific captimes enable better predictions of larger runtimes.

10. Conclusions

The paper advances runtime prediction for hard combinatorial problems through new models, algorithm-parameter inputs, and features for SAT, MIP, and TSP. Across 11 algorithms and 35 instance distributions, random forests and approximate Gaussian processes achieve the best reported performance across multiple generalization settings.

  • Study scope: The study evaluates runtime models for 11 algorithms across 35 SAT, MIP, and TSP instance distributions.It compares new approaches with a comprehensive set of methods from the literature.
  • Findings: The new approaches, chiefly random forests, perform best for new instances, new parameter settings, and both simultaneously.The conclusion covers parameterless and parameterized algorithm prediction settings.

Appendix A. Details on Benchmark Instance Sets

The appendix clarifies that SAT benchmark size statistics use the original instances before preprocessing. This distinction explains differences from some previously reported values.

  • Reporting convention: SAT benchmark variable and clause counts are reported for original instances before preprocessing.The appendix notes that preprocessing conventions explain differences from values reported in for IBM and SWV.

Appendix A.1. SAT benchmarks

The SAT benchmarks combine industrial, handmade, random, verification, and satisfiable-instance collections with widely varying sizes and provenance. COMPETITION is the union of the industrial, handmade, and random competition sets.

  • Competition benchmarks: INDU contains 1,676 industrial SAT-competition instances, averaging 111,000 variables and 689,187 clauses.Its maxima reach 9,685,434 variables and 14,586,886 clauses.
  • Competition benchmarks: HAND contains 1,955 handmade SAT-competition instances, averaging 4,968 variables and 82,594 clauses.The largest instance has 270,000 variables and 4,333,038 clauses.
  • Competition benchmarks: RAND contains 3,381 random SAT-competition instances, averaging 1,048 variables and 6,626 clauses.The maximum sizes are 19,000 variables and 79,800 clauses.
  • Competition benchmarks: COMPETITION is the union of INDU, HAND, and RAND.
  • Verification benchmarks: IBM contains 765 SAT-encoded bounded-model-checking instances selected from 40 randomly chosen IBM verification folders.The instances average 96,454 variables and 413,143 clauses.
  • Verification benchmarks: SWV contains 604 SAT-encoded software-verification instances generated for five programs.The programs include Dspam, HyperSAT, Wine, gzip, and xinetd.
  • Satisfiable benchmarks: RANDSAT contains 2,076 satisfiable instances from RAND, each proved by at least one winning solver in prior SAT competitions.These instances average 1,380 variables and 8,042 clauses.

Appendix A.2. MIP benchmarks

The MIP benchmarks comprise heterogeneous, real-world, computational-sustainability, and combinatorial-auction instance sets with widely varying sizes and structures.

  • BIGMIX contains 1,510 heterogeneous publicly available MILP instances, averaging 8,610 variables and 4,250 constraints.The largest instances have 550,539 variables and 550,339 constraints.
  • CORLAT contains 2,000 wildlife-corridor MILP instances, each with 466 variables and an average of 486 constraints.Constraint counts have standard deviation 25.2 and maximum 551.
  • RCW contains 1,980 instances modeling endangered red-cockaded woodpecker spread under land-protection decisions.The instances were generated across combinations of nine maps and eleven budgets.
  • REG contains 2,000 MILP-encoded winner-determination instances generated from combinatorial-auction regions.The generator sampled bids uniformly from 750 to 1,250 while fixing the bids/goods ratio at 3.91.

Appendix A.3. TSP benchmarks

The TSP benchmarks combine large random Euclidean, clustered Euclidean, and selected repository instances spanning roughly 100 to 5,934 nodes.

  • RUE contains 4,993 uniformly random Euclidean TSP instances with 100 to 1,600 nodes.The instances average 849 nodes, with standard deviation 429 and maximum 1,599.
  • RCE contains 5,001 random clustered Euclidean TSP instances with 100 to 1,600 nodes and clusters set to 1% of node count.The instances average 852 nodes, with standard deviation 432 and maximum 1,599.
  • TSPLIB contributes 63 repository instances whose feature computations completed successfully with both evaluated codebases.These instances range from 100 to 5,934 nodes and average 931 ± 1,376 nodes.
Loading 1211.0906v2…