An Empirical Study of Per-instance Algorithm Scheduling

verfasst von

Marius Lindauer, Rolf David Bergdoll, Frank Hutter

Abstract

Algorithm selection is a prominent approach to improve a system’s performance by selecting a well-performing algorithm from a portfolio for an instance at hand. One extension of the traditional algorithm selection problem is to not only select one single algorithm but a schedule of algorithms to increase robustness. Some approaches exist for solving this problem of selecting schedules on a per-instance basis (e.g., the Sunny and 3S systems), but to date, a fair and thorough comparison of these is missing. In this work, we implement Sunny’s approach and dynamic schedules inspired by 3S in the flexible algorithm selection framework flexfolio to use the same code base for a fair comparison. Based on the algorithm selection library (ASlib), we perform the first thorough empirical study on the strengths and weaknesses of per-instance algorithm schedules. We observe that on some domains it is crucial to use a training phase to limit the maximal size of schedules and to select the optimal neighborhood size of k-nearest-neighbor. By modifying our implemented variants of the Sunny and 3S approaches in this way, we achieve strong performance on many ASlib benchmarks and establish new state-of-the-art performance on 3 scenarios.

Externe Organisation(en)

Albert-Ludwigs-Universität Freiburg

Typ

Aufsatz in Konferenzband

Seiten

253-259

Anzahl der Seiten

7

Publikationsdatum

01.12.2016

Publikationsstatus

Veröffentlicht

Peer-reviewed

Ja

ASJC Scopus Sachgebiete

Theoretische Informatik, Informatik (insg.)

Elektronische Version(en)

https://doi.org/10.1007/978-3-319-50349-3_20 (Zugang: Geschlossen)