Publication Details

Details zu Publikationen

An Empirical Study of Per-instance Algorithm Scheduling

verfasst von
Marius Lindauer, Rolf David Bergdoll, Frank Hutter

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
Aufsatz in Konferenzband
Anzahl der Seiten
ASJC Scopus Sachgebiete
Theoretische Informatik, Informatik (insg.)
Elektronische Version(en) (Zugang: Geschlossen)