From Sequential Algorithm Selection to Parallel Portfolio Selection

authored by

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

Abstract

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

Type

Conference contribution

Pages

1-16

No. of pages

16

Publication date

29.05.2015

Publication status

Published

Peer reviewed

Yes

ASJC Scopus subject areas

Theoretical Computer Science, Computer Science(all)

Electronic version(s)

https://doi.org/10.1007/978-3-319-19084-6_1 (Access: Closed)