Learning Static Parallel Portfolios of Algorithms

Marek Petrik and Shlomo Zilberstein. Learning Static Parallel Portfolios of Algorithms. Proceedings of the Ninth International Symposium on Artificial Intelligence and Mathematics (ISAIM), Ft. Lauderdale, Florida, 2006.

Abstract

We present an approach for improving the performance of combinatorial optimization algorithms by generating an optimal 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 a method for finding a static PPA, in which the share of processor time allocated to each algorithm is fixed. The schedule is shown to be optimal with respect to a given training set of instances. We draw 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 (up to a factor of 2) over the fastest individual algorithm in a realistic setting.

Bibtex entry:

@inproceedings{PZisaim06,
  author	= {Marek Petrik and Shlomo Zilberstein},
  title		= {Learning Static Parallel Portfolios of Algorithms},
  booktitle     = {Proceedings of the Ninth International Symposium on Artificial
		   Intelligence and Mathematics},
  year		= {2006},
  pages		= {},
  address       = {Ft. Lauderdale, Florida},
  url		= {http://rbr.cs.umass.edu/shlomo/papers/PZisaim06.html}
}

shlomo@cs.umass.edu