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