Details
| Original language | English |
|---|---|
| Title of host publication | Learning and Intelligent Optimization |
| Editors | Paola Festa, Meinolf Sellmann, Joaquin Vanschoren |
| Publisher | Springer Verlag |
| Pages | 253-259 |
| Number of pages | 7 |
| ISBN (print) | 9783319503486 |
| Publication status | Published - 1 Dec 2016 |
| Externally published | Yes |
| Event | 10th International Conference on Learning and Intelligent Optimization, LION 10 - Ischia, Italy Duration: 29 May 2016 → 1 Jun 2016 |
Publication series
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volume | 10079 LNCS |
| ISSN (Print) | 0302-9743 |
| ISSN (electronic) | 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.
Keywords
- Algorithm schedules, Algorithm selection, Constraint solving
ASJC Scopus subject areas
- Mathematics(all)
- Theoretical Computer Science
- Computer Science(all)
- General Computer Science
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
Learning and Intelligent Optimization. ed. / Paola Festa; Meinolf Sellmann; Joaquin Vanschoren. Springer Verlag, 2016. p. 253-259 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10079 LNCS).
Research output: Chapter in book/report/conference proceeding › Conference contribution › Research › peer review
}
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 -