Details
| Originalsprache | Englisch |
|---|---|
| Titel des Sammelwerks | Handbook of Parallel Constraint Reasoning |
| Herausgeber (Verlag) | Springer International Publishing AG |
| Seiten | 583-615 |
| Seitenumfang | 33 |
| ISBN (elektronisch) | 9783319635163 |
| ISBN (Print) | 9783319635156 |
| Publikationsstatus | Veröffentlicht - 6 Apr. 2018 |
| Extern publiziert | Ja |
Abstract
In recent years the availability of parallel computation resources has grown rapidly. Nevertheless, even for the most widely studied constraint programming problems such as SAT, solver development and applications remain largely focussed on sequential rather than parallel approaches. To ease the burden usually associated with designing, implementing and testing parallel solvers, in this chapter, we demonstrate how methods from automatic algorithm design can be used to construct effective parallel portfolio solvers from sequential components. Specifically, we discuss two prominent approaches for this problem. (I) Parallel portfolio selection involves selecting a parallel portfolio consisting of complementary sequential solvers for a specific instance to be solved (as characterised by cheaply computable instance features). Applied to a broad set of sequential SAT solvers from SAT competitions, we show that our generic approach achieves nearly linear speedup on application instances, and super-linear speedups on combinatorial and random instances. (II) Automatic construction of parallel portfolios via algorithm configuration involves a parallel portfolio of algorithm parameter configurations that is optimized for a given set of instances. Applied to gold-medal-winning parameterized SAT solvers, we show that our approach can produce significantly better-performing SAT solvers than state-ofthe- art parallel solvers constructed by human experts, reducing time-outs by 17% and running time (PAR10 score) by 13% under competition conditions.
ASJC Scopus Sachgebiete
- Informatik (insg.)
- Allgemeine Computerwissenschaft
- Volkswirtschaftslehre, Ökonometrie und Finanzen (insg.)
- Betriebswirtschaft, Management und Rechnungswesen (insg.)
- Allgemeine Unternehmensführung und Buchhaltung
- Mathematik (insg.)
- Allgemeine Mathematik
Zitieren
- Standard
- Harvard
- Apa
- Vancouver
- BibTex
- RIS
Handbook of Parallel Constraint Reasoning. Springer International Publishing AG, 2018. S. 583-615.
Publikation: Beitrag in Buch/Bericht/Sammelwerk/Konferenzband › Beitrag in Buch/Sammelwerk › Forschung › Peer-Review
}
TY - CHAP
T1 - Selection and Configuration of Parallel Portfolios
AU - Lindauer, Marius
AU - Hoos, Holger
AU - Hutter, Frank
AU - Leyton-Brown, Kevin
PY - 2018/4/6
Y1 - 2018/4/6
N2 - In recent years the availability of parallel computation resources has grown rapidly. Nevertheless, even for the most widely studied constraint programming problems such as SAT, solver development and applications remain largely focussed on sequential rather than parallel approaches. To ease the burden usually associated with designing, implementing and testing parallel solvers, in this chapter, we demonstrate how methods from automatic algorithm design can be used to construct effective parallel portfolio solvers from sequential components. Specifically, we discuss two prominent approaches for this problem. (I) Parallel portfolio selection involves selecting a parallel portfolio consisting of complementary sequential solvers for a specific instance to be solved (as characterised by cheaply computable instance features). Applied to a broad set of sequential SAT solvers from SAT competitions, we show that our generic approach achieves nearly linear speedup on application instances, and super-linear speedups on combinatorial and random instances. (II) Automatic construction of parallel portfolios via algorithm configuration involves a parallel portfolio of algorithm parameter configurations that is optimized for a given set of instances. Applied to gold-medal-winning parameterized SAT solvers, we show that our approach can produce significantly better-performing SAT solvers than state-ofthe- art parallel solvers constructed by human experts, reducing time-outs by 17% and running time (PAR10 score) by 13% under competition conditions.
AB - In recent years the availability of parallel computation resources has grown rapidly. Nevertheless, even for the most widely studied constraint programming problems such as SAT, solver development and applications remain largely focussed on sequential rather than parallel approaches. To ease the burden usually associated with designing, implementing and testing parallel solvers, in this chapter, we demonstrate how methods from automatic algorithm design can be used to construct effective parallel portfolio solvers from sequential components. Specifically, we discuss two prominent approaches for this problem. (I) Parallel portfolio selection involves selecting a parallel portfolio consisting of complementary sequential solvers for a specific instance to be solved (as characterised by cheaply computable instance features). Applied to a broad set of sequential SAT solvers from SAT competitions, we show that our generic approach achieves nearly linear speedup on application instances, and super-linear speedups on combinatorial and random instances. (II) Automatic construction of parallel portfolios via algorithm configuration involves a parallel portfolio of algorithm parameter configurations that is optimized for a given set of instances. Applied to gold-medal-winning parameterized SAT solvers, we show that our approach can produce significantly better-performing SAT solvers than state-ofthe- art parallel solvers constructed by human experts, reducing time-outs by 17% and running time (PAR10 score) by 13% under competition conditions.
UR - http://www.scopus.com/inward/record.url?scp=85053996010&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-63516-3_15
DO - 10.1007/978-3-319-63516-3_15
M3 - Contribution to book/anthology
AN - SCOPUS:85053996010
SN - 9783319635156
SP - 583
EP - 615
BT - Handbook of Parallel Constraint Reasoning
PB - Springer International Publishing AG
ER -