An Empirical Study of Per-instance Algorithm Scheduling

Publikation: Beitrag in Buch/Bericht/Sammelwerk/KonferenzbandAufsatz in KonferenzbandForschungPeer-Review

Autorschaft

Externe Organisationen

  • Albert-Ludwigs-Universität Freiburg
Forschungs-netzwerk anzeigen

Details

OriginalspracheEnglisch
Titel des SammelwerksLearning and Intelligent Optimization
Herausgeber/-innenPaola Festa, Meinolf Sellmann, Joaquin Vanschoren
Herausgeber (Verlag)Springer Verlag
Seiten253-259
Seitenumfang7
ISBN (Print)9783319503486
PublikationsstatusVeröffentlicht - 1 Dez. 2016
Extern publiziertJa
Veranstaltung10th International Conference on Learning and Intelligent Optimization, LION 10 - Ischia, Italien
Dauer: 29 Mai 20161 Juni 2016

Publikationsreihe

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Band10079 LNCS
ISSN (Print)0302-9743
ISSN (elektronisch)1611-3349

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.

ASJC Scopus Sachgebiete

Zitieren

An Empirical Study of Per-instance Algorithm Scheduling. / Lindauer, Marius; Bergdoll, Rolf David; Hutter, Frank.
Learning and Intelligent Optimization. Hrsg. / Paola Festa; Meinolf Sellmann; Joaquin Vanschoren. Springer Verlag, 2016. S. 253-259 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Band 10079 LNCS).

Publikation: Beitrag in Buch/Bericht/Sammelwerk/KonferenzbandAufsatz in KonferenzbandForschungPeer-Review

Lindauer, M, Bergdoll, RD & Hutter, F 2016, An Empirical Study of Per-instance Algorithm Scheduling. in P Festa, M Sellmann & J Vanschoren (Hrsg.), Learning and Intelligent Optimization. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Bd. 10079 LNCS, Springer Verlag, S. 253-259, 10th International Conference on Learning and Intelligent Optimization, LION 10, Ischia, Italien, 29 Mai 2016. https://doi.org/10.1007/978-3-319-50349-3_20
Lindauer, M., Bergdoll, R. D., & Hutter, F. (2016). An Empirical Study of Per-instance Algorithm Scheduling. In P. Festa, M. Sellmann, & J. Vanschoren (Hrsg.), Learning and Intelligent Optimization (S. 253-259). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Band 10079 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-50349-3_20
Lindauer M, Bergdoll RD, Hutter F. An Empirical Study of Per-instance Algorithm Scheduling. in Festa P, Sellmann M, Vanschoren J, Hrsg., Learning and Intelligent Optimization. Springer Verlag. 2016. S. 253-259. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-50349-3_20
Lindauer, Marius ; Bergdoll, Rolf David ; Hutter, Frank. / An Empirical Study of Per-instance Algorithm Scheduling. Learning and Intelligent Optimization. Hrsg. / Paola Festa ; Meinolf Sellmann ; Joaquin Vanschoren. Springer Verlag, 2016. S. 253-259 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
Download
@inproceedings{774521a486e34f2f99b13b3b6f526581,
title = "An Empirical Study of Per-instance Algorithm Scheduling",
abstract = "Algorithm selection is a prominent approach to improve a system{\textquoteright}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{\textquoteright}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.",
keywords = "Algorithm schedules, Algorithm selection, Constraint solving",
author = "Marius Lindauer and Bergdoll, {Rolf David} and Frank Hutter",
year = "2016",
month = dec,
day = "1",
doi = "10.1007/978-3-319-50349-3_20",
language = "English",
isbn = "9783319503486",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "253--259",
editor = "Paola Festa and Meinolf Sellmann and Joaquin Vanschoren",
booktitle = "Learning and Intelligent Optimization",
address = "Germany",
note = "10th International Conference on Learning and Intelligent Optimization, LION 10 ; Conference date: 29-05-2016 Through 01-06-2016",

}

Download

TY - GEN

T1 - An Empirical Study of Per-instance Algorithm Scheduling

AU - Lindauer, Marius

AU - Bergdoll, Rolf David

AU - Hutter, Frank

PY - 2016/12/1

Y1 - 2016/12/1

N2 - 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.

AB - 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.

KW - Algorithm schedules

KW - Algorithm selection

KW - Constraint solving

UR - http://www.scopus.com/inward/record.url?scp=85006867149&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-50349-3_20

DO - 10.1007/978-3-319-50349-3_20

M3 - Conference contribution

AN - SCOPUS:85006867149

SN - 9783319503486

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 253

EP - 259

BT - Learning and Intelligent Optimization

A2 - Festa, Paola

A2 - Sellmann, Meinolf

A2 - Vanschoren, Joaquin

PB - Springer Verlag

T2 - 10th International Conference on Learning and Intelligent Optimization, LION 10

Y2 - 29 May 2016 through 1 June 2016

ER -

Von denselben Autoren