Learning Parallel Portfolios of Algorithms

Marek Petrik and Shlomo Zilberstein. Learning Parallel Portfolios of Algorithms. Annals of Mathematics and Artificial Intelligence, 48(1-2):85-106, 2006.

Abstract

A wide range of combinatorial optimization algorithms have been developed for complex reasoning tasks. Frequently, no single algorithm outperforms all the others. This has raised interest in leveraging the performance of a collection of algorithms to improve performance. We show how to accomplish this using a Parallel Portfolio of Algorithms (PPA). A PPA is a collection of diverse algorithms for solving a single problem, all running concurrently on a single processor until a solution is produced. The performance of the portfolio may be controlled by assigning different shares of processor time to each algorithm. We present an effective method for finding a PPA in which the share of processor time allocated to each algorithm is fixed. Finding the optimal static schedule is shown to be an NP-complete problem for a general class of utility functions. We present bounds on the performance of the PPA over random instances and evaluate the performance empirically on a collection of 23 state-of-the-art SAT algorithms. The results show significant performance gains over the fastest individual algorithm in the collection.

Bibtex entry:

@article{PZamai06,
  author	= {Marek Petrik and Shlomo Zilberstein},
  title		= {Learning Parallel Portfolios of Algorithms},
  journal	= {Annals of Mathematics and Artificial Intelligence},
  volume	= {48},
  number	= {1-2},
  year		= {2006},
  pages		= {85-106},
  url		= {http://rbr.cs.umass.edu/shlomo/papers/PZamai06.html}
}

shlomo@cs.umass.edu