Cloud computing
Computability
Learning
Artificial intelligence
Parallel algorithms
Randomised algorithms
Search problems
Travelling salesman problems
SAT instances
TSP instances
Cloud systems
Correlation coefficient
Machine learning
Parallel computation time
Parallel local search algorithms
Randomized algorithms
Sequential local search algorithms
Sequential runtime distributions
Algorithm design and analysis
Approximation algorithms
Machine learning algorithms
Prediction algorithms
Runtime
In cloud systems, computation time can be rented by the hour and for a given number of processors. Thus, accurate predictions of the behaviour of both sequential and parallel algorithms has become an important issue, in particular in the case of costly methods such as randomized combinatorial optimization tools. In this work, our objective is to use machine learning to predict performance of sequential and parallel local search algorithms. In addition to classical features of the instances used by other machine learning tools, we consider data on the sequential runtime distributions of a local search method. This allows us to predict with a high accuracy the parallel computation time of a large class of instances, by learning the behaviour of the sequential version of the algorithm on a small number of instances. Experiments with three solvers on SAT and TSP instances indicate that our method works well, with a correlation coefficient of up to 0.85 for SAT instances and up to 0.95 for TSP instances.