Algorithm runtime prediction: methods \& evaluation

DOI10.1016/J.ARTINT.2013.10.003zbMATH Open1334.68185DBLPjournals/ai/HutterXHL14OpenAlexW2964281761WikidataQ59585930 ScholiaQ59585930MaRDI QIDQ490455FDOQ490455

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

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)

zbMATH Keywords

mixed integer programmingpropositional satisfiabilityperformance predictionresponse surface modelstravelling salesperson problemsupervised machine learningempirical performance modelshighly parameterized algorithms

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Mixed integer programming (90C11)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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)

• 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
• MLP-ANN-based execution time prediction model and assessment of input parameters through structural modeling
• Major 2 satisfiability logic in discrete Hopfield neural network
• 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
• Empirical hardness models, methodology and a case study on combinatorial auctions
• Hybrid regression-classification models for algorithm selection
• 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
• 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

• MiniSat
• Zchaff2004
• SCIP
• lp_solve
• CPLEX
• Gurobi
• LKH
• Concorde
• SATzilla
• SPOT
• CryptoMiniSat
• minFunc
• SMAC
• PRMLT

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)