Algorithm runtime prediction: methods \& evaluation
From MaRDI portal
Publication:490455
DOI10.1016/J.ARTINT.2013.10.003zbMATH Open1334.68185DBLPjournals/ai/HutterXHL14arXiv1211.0906OpenAlexW2964281761WikidataQ59585930 ScholiaQ59585930MaRDI QIDQ490455FDOQ490455
Frank Hutter, Lin Xu, Kevin Leyton-Brown, Holger H. Hoos
Publication date: 27 August 2015
Published in: Artificial Intelligence (Search for Journal in Brave)
Abstract: 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.
Full work available at URL: https://arxiv.org/abs/1211.0906
Recommendations
- Empirical hardness models, methodology and a case study on combinatorial auctions
- Performance Prediction and Automated Tuning of Randomized and Parametric Algorithms
- Hybrid regression-classification models for algorithm selection
- Learning dynamic algorithm portfolios
- A Bayesian approach to tackling hard computational problems. (Preliminary report)
mixed integer programmingpropositional satisfiabilityperformance predictionresponse surface modelstravelling salesperson problemsupervised machine learningempirical performance modelshighly parameterized algorithms
Learning and adaptive systems in artificial intelligence (68T05) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Mixed integer programming (90C11)
Cites Work
- Theory and Applications of Satisfiability Testing
- Efficient global optimization of expensive black-box functions
- An effective implementation of the Lin-Kernighan traveling salesman heuristic
- The traveling salesman problem. A computational study.
- Theory and Applications of Satisfiability Testing
- Title not available (Why is that?)
- Random forests
- The design and analysis of computer experiments.
- Design and analysis of computer experiments. With comments and a rejoinder by the authors
- Gaussian processes for machine learning.
- Title not available (Why is that?)
- Pattern recognition and machine learning.
- Title not available (Why is that?)
- Regression Trees for Censored Data
- Title not available (Why is that?)
- Title not available (Why is that?)
- Lipschitzian optimization without the Lipschitz constant
- Theory and Applications of Satisfiability Testing
- SATzilla: portfolio-based algorithm selection for SAT
- Learning dynamic algorithm portfolios
- Heavy-tailed phenomena in satisfiability and constraint satisfaction problems
- Hierarchical Hardness Models for SAT
- Performance Prediction and Automated Tuning of Randomized and Parametric Algorithms
- Stochastic local search. Foundations and applications.
- Principles and Practice of Constraint Programming – CP 2004
- Measuring instance difficulty for combinatorial optimization problems
- A novel feature-based approach to characterize algorithm performance for the traveling salesperson problem
- Title not available (Why is that?)
- An Effective Heuristic Algorithm for the Traveling-Salesman Problem
- Estimating the Efficiency of Backtrack Programs
- Discovering the suitability of optimisation algorithms by learning from evolved instances
- Title not available (Why is that?)
- Correlated and uncorrelated fitness landscapes and how to tell the difference
- Response Surfaces, Mixtures, and Ridge Analyses
- Algorithm Survival Analysis
- Empirical hardness models
- Experimental research in evolutionary computation. The new experimentalism
- Mixed Models for the Analysis of Optimization Algorithms
- Online Estimation of SAT Solving Runtime
- Structural Abstraction of Software Verification Conditions
- Theory and Applications of Satisfiability Testing
- Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
Cited In (41)
- SUNNY-CP and the MiniZinc challenge
- How we designed winning algorithms for abstract argumentation and which insight we attained
- Automatic model training under restrictive time constraints
- A new class of hard problem instances for the 0-1 knapsack problem
- On learning and branching: a survey
- Wombit: a portfolio bit-vector solver using word-level propagation
- Portfolio approaches for constraint optimization problems
- Synergies between machine learning and reasoning -- an introduction by the Kay R. Amel group
- A PAC Approach to Application-Specific Algorithm Selection
- ASlib: a benchmark library for algorithm selection
- Online over time processing of combinatorial problems
- Portfolio theorem proving and prover runtime prediction for geometry
- The algorithm selection competitions 2015 and 2017
- A Classifier to Decide on the Linearization of Mixed-Integer Quadratic Problems in CPLEX
- Random sampling and machine learning to understand good decompositions
- On the empirical scaling of run-time for finding optimal solutions to the travelling salesman problem
- Features for the 0-1 knapsack problem based on inclusionwise maximal solutions
- Formal Concept Analysis
- Online Estimation of SAT Solving Runtime
- Dynamic algorithm selection for runtime concepts
- Automatic construction of optimal static sequential portfolios for AI planning and beyond
- Optimal decision trees for the algorithm selection problem: integer programming based approaches
- On the importance of domain model configuration for automated planning engines
- A Bayesian approach to tackling hard computational problems. (Preliminary report)
- Toward optimal probabilistic active learning using a Bayesian approach
- A machine learning approach to algorithm selection for \(\mathcal{NP}\)-hard optimization problems: a case study on the MPE problem
- Adaptive online scheduling of tasks with anytime property on heterogeneous resources
- Generation techniques for linear programming instances with controllable properties
- On the impact of configuration on abstract argumentation automated reasoning
- The configurable SAT solver challenge (CSSC)
- A data-driven \textit{meta}-learning recommendation model for multi-mode resource constrained project scheduling problem
- Empirical decision model learning
- A study on the effects of normalized TSP features for automated algorithm selection
- Major 2 Satisfiability Logic in Discrete Hopfield Neural Network
- Performance Prediction and Automated Tuning of Randomized and Parametric Algorithms
- Bayesian additive regression trees using Bayesian model averaging
- Combinatorial search from an energy perspective
- Efficient benchmarking of algorithm configurators via model-based surrogates
- Metalearning and algorithm selection: progress, state of the art and introduction to the 2018 special issue
- Algorithms for electric vehicle scheduling in large-scale mobility-on-demand schemes
- AutonoML: Towards an Integrated Framework for Autonomous Machine Learning
Uses Software
This page was built for publication: Algorithm runtime prediction: methods \& evaluation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q490455)
