Chapter 8 Selection and Configuration of Parallel Portfolios
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 speed up on application instances, and super linear speed ups 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. Marius Lindauer University of Freiburg, Germany, e mail: lindauer@cs.uni freiburg.de Holger Hoos University of British Columbia, Canada Leiden University, Netherlands, e mail: hoos@cs.ubc.