Details
| Original language | English |
|---|---|
| Title of host publication | Handbook of Parallel Constraint Reasoning |
| Publisher | Springer International Publishing AG |
| Pages | 583-615 |
| Number of pages | 33 |
| ISBN (electronic) | 9783319635163 |
| ISBN (print) | 9783319635156 |
| Publication status | Published - 6 Apr 2018 |
| Externally published | Yes |
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 subject areas
- Computer Science(all)
- General Computer Science
- Economics, Econometrics and Finance(all)
- Business, Management and Accounting(all)
- General Business,Management and Accounting
- Mathematics(all)
- General Mathematics
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
Handbook of Parallel Constraint Reasoning. Springer International Publishing AG, 2018. p. 583-615.
Research output: Chapter in book/report/conference proceeding › Contribution to book/anthology › Research › 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 -