Learning Parallel Portfolios of Algorithms
Marek Petrik
Shlomo Zilberstein
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.
Download
[pdf]