The DOI matches its Crossref record; 98 of the 98 references it cites were found in a registry or an index.
Algorithm runtime prediction: Methods & evaluation
Open accessAbstract
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Breiman, L. (2001) · Machine Learning · doi:10.1023/a:1010933404324 · Cited by 133,538
The Elements of Statistical Learning
Hastie, T., Tibshirani, R., & Friedman, J. (2009) · Springer Series in Statistics · doi:10.1007/978-0-387-84858-7 · Cited by 25,970
The Elements of Statistical Learning
Hastie, T., Friedman, J., & Tibshirani, R. (2001) · Springer Series in Statistics · doi:10.1007/978-0-387-21606-5 · Cited by 24,162
Classification and Regression Trees.
Gordon, A. D., Breiman, L., Friedman, J. H., Olshen, R. A., & Stone, C. J. (1984) · Biometrics · doi:10.2307/2530946 · Cited by 23,522
Book Review: Pattern Recognition and Machine Learning
Nasrabadi, N. M. (2007) · Journal of Electronic Imaging · doi:10.1117/1.2819119 · Cited by 22,066
Classification and Regression Trees.
Ryzin, J. V., Breiman, L., Friedman, J. H., Olshen, R. A., & Stone, C. J. (1986) · Journal of the American Statistical Association · doi:10.2307/2288003 · Cited by 20,825
(2021) · A First Course in Statistical Programming with R · doi:10.1017/9781108993456.011 · Cited by 13,724
Gaussian Processes for Machine Learning
Rasmussen, C. E., & Williams, C. K. I. (2005) · doi:10.7551/mitpress/3206.001.0001 · Cited by 11,705
Classification and regression trees
Praagman, J. (1985) · European Journal of Operational Research · doi:10.1016/0377-2217(85)90321-2 · Cited by 10,053
(2006) · Springer Series in Operations Research and Financial Engineering · doi:10.1007/978-0-387-40065-5 · Cited by 9,008
(2006) · Springer eBooks · Cited by 8,123
Efficient Global Optimization of Expensive Black-Box Functions
Jones, D. R., Schonlau, M., & Welch, W. J. (1998) · Journal of Global Optimization · doi:10.1023/a:1008306431147 · Cited by 8,070
(2012) · Cited by 8,009
Design and Analysis of Computer Experiments
Sacks, J., Welch, W. J., Mitchell, T. J., & Wynn, H. P. (1989) · Statistical Science · doi:10.1214/ss/1177012413 · Cited by 6,919
Pattern Recognition and Machine Learning
Neal, R. M. (2007) · Technometrics · doi:10.1198/tech.2007.s518 · Cited by 4,571
On the Experimental Attainment of Optimum Conditions
Box, G. E. P., & Wilson, K. B. (1951) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.2517-6161.1951.tb00067.x · Cited by 4,464
An Effective Heuristic Algorithm for the Traveling-Salesman Problem
Lin, S., & Kernighan, B. W. (1973) · Operations Research · doi:10.1287/opre.21.2.498 · Cited by 3,821
Eén, N., & Sörensson, N. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-24605-3_37 · Cited by 2,629
Sequential Model-Based Optimization for General Algorithm Configuration
Hutter, F., Hoos, H. H., & Leyton-Brown, K. (2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-25566-3_40 · Cited by 2,469
Self-citationA statistical approach to some basic mine valuation problems on the Witwatersrand
Krige, D. G. (1951) · Journal of the Southern African Institute of Mining and Metallurgy · Cited by 2,409
Lipschitzian optimization without the Lipschitz constant
Jones, D. R., Perttunen, C. D., & Stuckman, B. E. (1993) · Journal of Optimization Theory and Applications · doi:10.1007/bf00941892 · Cited by 1,976
Feature Extraction: Foundations and Applications (Studies in Fuzziness and Soft Computing)
Guyon, I., Gunn, S., Nikravesh, M., & Zadeh, L. A. (2006) · Springer eBooks · Cited by 1,845
The Traveling salesman problem: a computational study
(2007) · Choice Reviews Online · doi:10.5860/choice.45-0928 · Cited by 1,726
Feature extraction : foundations and applications
Guyon, I., Gunn, S. R., Nikravesh, M., & zadeh, L. N. (2006) · Cited by 1,658
An effective implementation of the Lin–Kernighan traveling salesman heuristic
Helsgaun, K. (2000) · European Journal of Operational Research · doi:10.1016/s0377-2217(99)00284-2 · Cited by 1,630
Meinshausen, N. (2006) · Cited by 1,521
Thompson, W. A., & Nelson, W. (1983) · Journal of the American Statistical Association · doi:10.2307/2288691 · Cited by 1,476
Stochastic Local Search: Foundations & Applications
Hoos, H. H., & St�tzle, T. (2004) · Medical Entomology and Zoology · Cited by 1,227
Self-citationThe Algorithm Selection Problem
Rice, J. R. (1976) · Advances in Computers · doi:10.1016/s0065-2458(08)60520-3 · Cited by 1,195
Netlab: Algorithms for Pattern Recognition
Nabney, I. T. (2002) · Cited by 1,161
A perspective view and survey of meta-learning
Vilalta, R., & Drissi, Y. (2002) · Artificial Intelligence Review · doi:10.1023/a:1019956318069 · Cited by 1,108
Where the really hard problems are
Cheeseman, P. C., Kanefsky, B., & Taylor, W. M. (1991) · Cited by 1,004
SATzilla: Portfolio-based Algorithm Selection for SAT
Xu, L., Hutter, F., Hoos, H. H., & Leyton-Brown, K. (2008) · Journal of Artificial Intelligence Research · doi:10.1613/jair.2490 · Cited by 857
Self-citationBishop, C. M. (2004) · Handbook of Neural Computation · doi:10.1887/0750303123/b365c43 · Cited by 833
Hard and easy distributions of SAT problems
Mitchell, D. G. M., Selman, B., & Levesque, H. J. (1992) · Cited by 799
Nordhausen, K. (2009) · International Statistical Review · doi:10.1111/j.1751-5823.2009.00095_18.x · Cited by 637
Response Surfaces, Mixtures, and Ridge Analyses
Box, G. E. P., & Draper, N. R. (2007) · Wiley Series in Probability and Statistics · doi:10.1002/0470072768 · Cited by 618
Correlated and uncorrelated fitness landscapes and how to tell the difference
Weinberger, E. (1990) · Biological Cybernetics · doi:10.1007/bf00202749 · Cited by 561
Cross-disciplinary perspectives on meta-learning for algorithm selection
Smith-Miles, K. A. (2009) · ACM Computing Surveys · doi:10.1145/1456650.1456656 · Cited by 552
(2007) · The MIT Press eBooks · doi:10.7551/mitpress/7496.001.0001 · Cited by 536
Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations
Etessami, K., & Yannakakis, M. (2009) · Journal of the ACM · doi:10.1145/1462153.1462154 · Cited by 512
Regression Trees for Censored Data
Segal, M. R. (1988) · Biometrics · doi:10.2307/2531894 · Cited by 495
Fast Sparse Gaussian Process Methods: The Informative Vector Machine
Herbrich, R., Lawrence, N. D., & Seeger, M. (2002) · neural information processing systems · Cited by 488
Fitness Distance Correlation as a Measure of Problem Difficulty for Genetic Algorithms
Jones, T., & Forrest, S. (1995) · Cited by 469
Tresp, V. (2000) · Neural Computation · doi:10.1162/089976600300014908 · Cited by 402
Heavy-Tailed Phenomena in Satisfiability and Constraint Satisfaction Problems
Gomes, C. P., Selman, B., Crato, N., & Kautz, H. (2000) · Journal of Automated Reasoning · doi:10.1023/a:1006314320276 · Cited by 395
Experimental Methods for the Analysis of Optimization Algorithms
(2010) · Springer eBooks · doi:10.1007/978-3-642-02538-9 · Cited by 333
Meta-Learning by Landmarking Various Learning Algorithms
Pfahringer, B., Bensusan, H. N., & Giraud-Carrier, C. G. (2000) · Cited by 302
Sequential Parameter Optimization
Bartz-Beielstein, T., Lasarczyk, C. W. G., & Preuss, M. (2005) · 2005 IEEE Congress on Evolutionary Computation · doi:10.1109/cec.2005.1554761 · Cited by 300
A survey of recent advances in SAT-based formal verification
Prasad, M. R., Biere, A., & Gupta, A. (2005) · International Journal on Software Tools for Technology Transfer · doi:10.1007/s10009-004-0183-4 · Cited by 279
Hothorn, T., Lausen, B., Benner, A., & Radespiel‐Tröger, M. (2004) · Statistics in Medicine · doi:10.1002/sim.1593 · Cited by 246
Pace—A Toolset for the Performance Prediction of Parallel and Distributed Systems
Nudd, G. R., Kerbyson, D. J., Papaefstathiou, E., Perry, S. C., Harper, J. S., & Wilcox, D. V. (2000) · The International Journal of High Performance Computing Applications · doi:10.1177/109434200001400306 · Cited by 235
Measuring instance difficulty for combinatorial optimization problems
Smith-Miles, K., & Lopes, L. (2012) · Computers & Operations Research · doi:10.1016/j.cor.2011.07.006 · Cited by 210
Scaling and Probabilistic Smoothing: Efficient Dynamic Local Search for SAT
Hutter, F., Tompkins, D. A. D., & Hoos, H. H. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-46135-3_16 · Cited by 204
Self-citationExperimental Research in Evolutionary Computation
(2006) · Natural Computing Series · doi:10.1007/3-540-32027-x · Cited by 199
ISAC – Instance-Specific Algorithm Configuration
Kadıoğlu, S., Malitsky, Y., Sellmann, M., & Tierney, K. (2010) · Frontiers in artificial intelligence and applications · doi:10.3233/978-1-60750-606-5-751 · Cited by 192
Hydra: Automatically Configuring Algorithms for Portfolio-Based Selection
Xu, L., Hoos, H., & Leyton-Brown, K. (2010) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v24i1.7565 · Cited by 188
Self-citationUnderstanding Random SAT: Beyond the Clauses-to-Variables Ratio
Nudelman, E., Leyton-Brown, K., Hoos, H. H., Devkar, A., & Shoham, Y. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-30201-8_33 · Cited by 183
Self-citationBartz–Beielstein, T. (2010) · Cited by 180
Approximation Methods for Gaussian Process Regression
Quiñonero-Candela, J., Rasmussen, C. E., & Williams, C. K. I. (2007) · Large-Scale Kernel Machines · doi:10.7551/mitpress/7496.003.0011 · Cited by 179
Weiss, N. A. (2005) · CERN Document Server (European Organization for Nuclear Research) · Cited by 178
Automated Configuration of Mixed Integer Programming Solvers
Hutter, F., Hoos, H. H., & Leyton‐Brown, K. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-13520-0_23 · Cited by 166
Self-citationFast Sparse Gaussian Process Methods: The Informative Vector Machine
Lawrence, N. D., Seeger, M., & Herbrich, R. (2003) · Infoscience (Ecole Polytechnique Fédérale de Lausanne) · Cited by 165
Predicting Execution Time of Computer Programs Using Sparse Polynomial Regression
Huang, L., Jia, J., Yu, B., Chun, B.-G., Maniatis, P., & Naik, M. (2011) · Cited by 162
Relevance estimation and value calibration of evolutionary algorithm parametersPreprint
Nannen, V., & Eiben, A. E. (2007) · Cited by 157
Bagging Survival TreesPreprint
Hothorn, T., Lausen, B., Benner, A., & Radespiel‐Tröger, M. (2002) · SSRN Electronic Journal · Cited by 153
Empirical hardness models: Methodology and a case study on combinatorial auctions
Leyton‐Brown, K., Nudelman, E., & Shoham, Y. (2009) · Journal of the ACM · doi:10.1145/1538902.1538906 · Cited by 151
Self-citationZchaff2004: An Efficient SAT Solver
Mahajan, Y. S., Fu, Z., & Malik, S. (2005) · Lecture notes in computer science · doi:10.1007/11527695_27 · Cited by 147
Automated configuration of algorithms for solving hard computational problems
Hutter, F. (2009) · cIRcle (University of British Columbia) · doi:10.14288/1.0051652 · Cited by 141
Self-citationThe Design and Analysis of Computer Experiments
Deng, L. (2004) · Technometrics · doi:10.1198/tech.2004.s230 · Cited by 127
Evaluating Component Solver Contributions to Portfolio-Based Algorithm Selectors
Xu, L., Hutter, F., Hoos, H. H., & Leyton‐Brown, K. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-31612-8_18 · Cited by 125
Self-citationAn experimental investigation of model-based parameter optimisation: SPO and beyond
Hutter, F., Hoos, H. H., Leyton‐Brown, K., & Murphy, K. P. (2009) · Genetic and Evolutionary Computation Conference (GECCO) · doi:10.1145/1569901.1569940 · Cited by 122
Self-citationDiscovering the suitability of optimisation algorithms by learning from evolved instances
Smith‐Miles, K., & Hemert, J. I. V. (2011) · Annals of Mathematics and Artificial Intelligence · doi:10.1007/s10472-011-9230-5 · Cited by 117
A Bayesian Approach to Tackling Hard Computational ProblemsPreprint
Horvitz, E., Ruan, Y., Gomes, C. P., Kautz, H., Selman, B., & Chickering, D. M. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1301.2279 · Cited by 114
SATzilla-07: The Design and Analysis of an Algorithm Portfolio for SAT
Xu, L. H., Hutter, F., Hoos, H. H., & Leyton‐Brown, K. (2007) · Springer eBooks · doi:10.1007/978-3-540-74970-7_50 · Cited by 109
Self-citationMersmann, O., Bischl, B., Trautmann, H., Wagner, M., Bossek, J., & Neumann, F. (2013) · Annals of Mathematics and Artificial Intelligence · doi:10.1007/s10472-013-9341-2 · Cited by 108
High-level optimization via automated statistical modeling
Brewer, E. A. (1995) · ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming · doi:10.1145/209936.209946 · Cited by 96
Boosting Verification by Automatic Tuning of Decision Procedures
Hutter, F., Babić, D., Hoos, H. H., & Hu, A. J. (2007) · doi:10.1109/fmcad.2007.13 · Cited by 95
Self-citationAn evaluation of machine learning in algorithm selection for search problems
Kotthoff, L., Gent, I. P., & Miguel, I. (2012) · AI Communications · doi:10.3233/aic-2012-0533 · Cited by 93
Identifying Key Algorithm Parameters and Instance Features Using Forward Selection
Hutter, F., Hoos, H. H., & Leyton‐Brown, K. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-44973-4_40 · Cited by 89
Self-citationTuning search algorithms for real-world applications: a regression tree based approach
Bartz–Beielstein, T., & Markon, S. (2004) · IEEE Congress on Evolutionary Computation (CEC) · doi:10.1109/cec.2004.1330986 · Cited by 89
Parallel Algorithm Configuration
Hutter, F., Hoos, H. H., & Leyton‐Brown, K. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-34413-8_5 · Cited by 82
Self-citationInstance-Specific Algorithm Configuration
Malitsky, Y. (2014) · Springer eBooks · doi:10.1007/978-3-319-11230-5 · Cited by 78
Time-Bounded Sequential Parameter Optimization
Hutter, F., Hoos, H. H., Leyton‐Brown, K., & Murphy, K. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-13800-3_30 · Cited by 76
Self-citationHow to solve it automatically: selection among problem-solving methods
Fink, E. (1998) · Cited by 72
Understanding the empirical hardness of NP -complete problems
Leyton‐Brown, K., Hoos, H. H., Hutter, F., & Xu, L. (2014) · Communications of the ACM · doi:10.1145/2594413.2594424 · Cited by 63
Self-citationExploiting Competitive Planner Performance
Howe, A. E., Dahlman, E., Hansen, C., Scheetz, M., & von Mayrhauser, A. (2000) · Lecture notes in computer science · doi:10.1007/10720246_5 · Cited by 62
Structural Abstraction of Software Verification Conditions
Babić, D., & Hu, A. J. (2007) · Springer eBooks · doi:10.1007/978-3-540-73368-3_41 · Cited by 62
Boosting as a Metaphor for Algorithm Design
Leyton‐Brown, K., Nudelman, E., Andrew, G., McFadden, J., & Shoham, Y. (2003) · Lecture notes in computer science · doi:10.1007/978-3-540-45193-8_75 · Cited by 57
Self-citationTuning the Performance of the MMAS Heuristic
Ridge, E., & Kudenko⋆, D. (2007) · Springer eBooks · doi:10.1007/978-3-540-74446-7_4 · Cited by 52
Measuring algorithm footprints in instance space
Smith‐Miles, K., & Tan, T. T. (2012) · IEEE Congress on Evolutionary Computation (CEC) · doi:10.1109/cec.2012.6252992 · Cited by 38
Tradeoffs in the empirical evaluation of competing algorithm designs
Hutter, F., Hoos, H. H., & Leyton‐Brown, K. (2010) · Annals of Mathematics and Artificial Intelligence · doi:10.1007/s10472-010-9191-0 · Cited by 36
Self-citationGagliolo, M., & Schmidhuber, J. (2006) · Cited by 35
Bayesian Optimization With Censored Response DataPreprint
Hutter, F., Hoos, H., & Leyton-Brown, K. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1310.1947 · Cited by 33
Self-citationGaussian Process Models for Censored Sensor Readings
Ertin, E. (2007) · IEEE/SP Workshop on Statistical Signal Processing (SSP) · doi:10.1109/ssp.2007.4301342 · Cited by 31
Hutter, F. (2007) · Cited by 27
Self-citationSmith, S. W. (2003) · Digital Signal Processing · doi:10.1016/b978-0-7506-7444-7/50046-7 · Cited by 13
Gagliolo, M., & LeGrand, C. C. (2010) · Springer eBooks · doi:10.1007/978-3-642-02538-9_7 · Cited by 11
Cited by
Automated Algorithm Selection: Survey and Perspectives
Kerschke, P., Hoos, H. H., Neumann, F., & Trautmann, H. (2019) · Evolutionary Computation · doi:10.1162/evco_a_00242 · Cited by 435
Self-citationVanschoren, J. (2019) · The Springer Series on Challenges in Machine Learning · doi:10.1007/978-3-030-05318-5_2 · Cited by 328
Performance-influence models for highly configurable systems
Siegmund, N., Grebhahn, A., Apel, S., & Kästner, C. (2015) · Proceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering · doi:10.1145/2786805.2786845 · Cited by 267
Metadata
- Authors
- Hutter, F., Xu, L., Hoos, H. H., & Leyton-Brown, K.
- Venue
- Artificial Intelligence
- Publisher
- Elsevier BV
- Published
- 2014-01
- Volume
- 206
- Pages
- 79-111
- ISSN
- 0004-3702 (ISSN-L)
- OpenAlex
- W2964281761
- Cited by
- 395
- References
- 98
- FWCI
- 33.92
- Type
- journal article
- Language
- en
- Open access
- bronze
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.