Algorithm runtime prediction: methods \& evaluation
From MaRDI portal
Publication:490455
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.
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)
Cites work
- scientific article; zbMATH DE number 1680164 (Why is no real title available?)
- scientific article; zbMATH DE number 3860199 (Why is no real title available?)
- scientific article; zbMATH DE number 67483 (Why is no real title available?)
- scientific article; zbMATH DE number 6276119 (Why is no real title available?)
- scientific article; zbMATH DE number 5060482 (Why is no real title available?)
- scientific article; zbMATH DE number 3067118 (Why is no real title available?)
- A novel feature-based approach to characterize algorithm performance for the traveling salesperson problem
- Algorithm survival analysis
- An Effective Heuristic Algorithm for the Traveling-Salesman Problem
- An effective implementation of the Lin-Kernighan traveling salesman heuristic
- Correlated and uncorrelated fitness landscapes and how to tell the difference
- Design and analysis of computer experiments. With comments and a rejoinder by the authors
- Discovering the suitability of optimisation algorithms by learning from evolved instances
- Efficient global optimization of expensive black-box functions
- Empirical hardness models, methodology and a case study on combinatorial auctions
- Estimating the Efficiency of Backtrack Programs
- Experimental research in evolutionary computation. The new experimentalism
- Gaussian processes for machine learning.
- Heavy-tailed phenomena in satisfiability and constraint satisfaction problems
- Hierarchical Hardness Models for SAT
- Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
- Learning dynamic algorithm portfolios
- Lipschitzian optimization without the Lipschitz constant
- Measuring instance difficulty for combinatorial optimization problems
- Mixed models for the analysis of optimization algorithms
- Online Estimation of SAT Solving Runtime
- Pattern recognition and machine learning.
- Performance Prediction and Automated Tuning of Randomized and Parametric Algorithms
- Principles and Practice of Constraint Programming – CP 2004
- Quantile regression forests
- Random forests
- Regression Trees for Censored Data
- Response Surfaces, Mixtures, and Ridge Analyses
- SATzilla: portfolio-based algorithm selection for SAT
- Stochastic local search. Foundations and applications.
- Structural Abstraction of Software Verification Conditions
- The design and analysis of computer experiments.
- The traveling salesman problem. A computational study.
- Theory and Applications of Satisfiability Testing
- Theory and Applications of Satisfiability Testing
- Theory and Applications of Satisfiability Testing
- Theory and Applications of Satisfiability Testing
Cited in
(44)- A Classifier to Decide on the Linearization of Mixed-Integer Quadratic Problems in CPLEX
- On the importance of domain model configuration for automated planning engines
- Generation techniques for linear programming instances with controllable properties
- Portfolio approaches for constraint optimization problems
- Adaptive online scheduling of tasks with anytime property on heterogeneous resources
- A Bayesian approach to tackling hard computational problems. (Preliminary report)
- Bayesian additive regression trees using Bayesian model averaging
- MLP-ANN-based execution time prediction model and assessment of input parameters through structural modeling
- ASlib: a benchmark library for algorithm selection
- Major 2 satisfiability logic in discrete Hopfield neural network
- Dynamic algorithm selection for runtime concepts
- On the impact of configuration on abstract argumentation automated reasoning
- Toward optimal probabilistic active learning using a Bayesian approach
- How we designed winning algorithms for abstract argumentation and which insight we attained
- Combinatorial search from an energy perspective
- Online over time processing of combinatorial problems
- Portfolio theorem proving and prover runtime prediction for geometry
- Automatic model training under restrictive time constraints
- Synergies between machine learning and reasoning -- an introduction by the Kay R. Amel group
- Random sampling and machine learning to understand good decompositions
- Automatic construction of optimal static sequential portfolios for AI planning and beyond
- A data-driven \textit{meta}-learning recommendation model for multi-mode resource constrained project scheduling problem
- Hybrid regression-classification models for algorithm selection
- 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
- A PAC Approach to Application-Specific Algorithm Selection
- A study on the effects of normalized TSP features for automated algorithm selection
- A machine learning approach to algorithm selection for \(\mathcal{NP}\)-hard optimization problems: a case study on the MPE problem
- A new class of hard problem instances for the 0-1 knapsack problem
- Online Estimation of SAT Solving Runtime
- AutonoML: Towards an Integrated Framework for Autonomous Machine Learning
- SUNNY-CP and the MiniZinc challenge
- Features for the 0-1 knapsack problem based on inclusionwise maximal solutions
- The configurable SAT solver challenge (CSSC)
- The algorithm selection competitions 2015 and 2017
- Empirical hardness models, methodology and a case study on combinatorial auctions
- Empirical decision model learning
- Formal Concept Analysis
- Performance Prediction and Automated Tuning of Randomized and Parametric Algorithms
- Optimal decision trees for the algorithm selection problem: integer programming based approaches
- On learning and branching: a survey
- Wombit: a portfolio bit-vector solver using word-level propagation
- On the empirical scaling of run-time for finding optimal solutions to the travelling salesman problem
Describes a project that uses
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)
