Publications Details

Publication Details

From Sequential Algorithm Selection to Parallel Portfolio Selection

authored by
M. Lindauer, Holger H. Hoos, F. Hutter

In view of the increasing importance of hardware parallelism, a natural extension of per-instance algorithm selection is to select a set of algorithms to be run in parallel on a given problem instance, based on features of that instance. Here, we explore how existing algorithm selection techniques can be effectively parallelized. To this end, we leverage the machine learning models used by existing sequential algorithm selectors, such as 3S, ISAC, SATzilla and ME-ASP, and modify their selection procedures to produce a ranking of the given candidate algorithms; we then select the top n algorithms under this ranking to be run in parallel on n processing units. Furthermore, we adapt the pre-solving schedules obtained by aspeed to be effective in a parallel setting with different time budgets for each processing unit. Our empirical results demonstrate that, using 4 processing units, the best of our methods achieves a 12-fold average speedup over the best single solver on a broad set of challenging scenarios from the algorithm selection library.

External Organisation(s)
University of Freiburg
University of British Columbia
Conference contribution
No. of pages
Publication date
Publication status
Peer reviewed
ASJC Scopus subject areas
Theoretical Computer Science, Computer Science(all)
Electronic version(s) (Access: Closed)