From Sequential Algorithm Selection to Parallel Portfolio Selection

verfasst von

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.

Externe Organisation(en)

Albert-Ludwigs-Universität Freiburg
University of British Columbia

Typ

Aufsatz in Konferenzband

Seiten

1-16

Anzahl der Seiten

16

Publikationsdatum

29.05.2015

Publikationsstatus

Veröffentlicht

Peer-reviewed

Ja

ASJC Scopus Sachgebiete

Theoretische Informatik, Informatik (insg.)

Elektronische Version(en)

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