Details
| Originalsprache | Englisch |
|---|---|
| Titel des Sammelwerks | Learning and Intelligent Optimization |
| Herausgeber/-innen | Clarisse Dhaenens, Laetitia Jourdan, Marie-Eleonore Marmion |
| Herausgeber (Verlag) | Springer Verlag |
| Seiten | 1-16 |
| Seitenumfang | 16 |
| ISBN (Print) | 9783319190839 |
| Publikationsstatus | Veröffentlicht - 29 Mai 2015 |
| Extern publiziert | Ja |
| Veranstaltung | 9th International Conference on Learning and Intelligent Optimization, LION 2015 - Lille, Frankreich Dauer: 12 Jan. 2015 → 15 Jan. 2015 |
Publikationsreihe
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Band | 8994 |
| ISSN (Print) | 0302-9743 |
| ISSN (elektronisch) | 1611-3349 |
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.
ASJC Scopus Sachgebiete
- Mathematik (insg.)
- Theoretische Informatik
- Informatik (insg.)
- Allgemeine Computerwissenschaft
Zitieren
- Standard
- Harvard
- Apa
- Vancouver
- BibTex
- RIS
Learning and Intelligent Optimization. Hrsg. / Clarisse Dhaenens; Laetitia Jourdan; Marie-Eleonore Marmion. Springer Verlag, 2015. S. 1-16 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Band 8994).
Publikation: Beitrag in Buch/Bericht/Sammelwerk/Konferenzband › Aufsatz in Konferenzband › Forschung › Peer-Review
}
TY - GEN
T1 - From Sequential Algorithm Selection to Parallel Portfolio Selection
AU - Lindauer, M.
AU - Hoos, Holger H.
AU - Hutter, F.
PY - 2015/5/29
Y1 - 2015/5/29
N2 - 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.
AB - 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.
KW - Algorithm selection
KW - Answer set programming
KW - Constraint solving
KW - Parallel portfolios
UR - http://www.scopus.com/inward/record.url?scp=84942419507&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-19084-6_1
DO - 10.1007/978-3-319-19084-6_1
M3 - Conference contribution
AN - SCOPUS:84942419507
SN - 9783319190839
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 1
EP - 16
BT - Learning and Intelligent Optimization
A2 - Dhaenens, Clarisse
A2 - Jourdan, Laetitia
A2 - Marmion, Marie-Eleonore
PB - Springer Verlag
T2 - 9th International Conference on Learning and Intelligent Optimization, LION 2015
Y2 - 12 January 2015 through 15 January 2015
ER -