  It has been widely observed that there is no single "dominant" SAT solver;
instead, different solvers perform best on different instances. Rather than
following the traditional approach of choosing the best solver for a given
class of instances, we advocate making this decision online on a per-instance
basis. Building on previous work, we describe SATzilla, an automated approach
for constructing per-instance algorithm portfolios for SAT that use so-called
empirical hardness models to choose among their constituent solvers. This
approach takes as input a distribution of problem instances and a set of
component solvers, and constructs a portfolio optimizing a given objective
function (such as mean runtime, percent of instances solved, or score in a
competition). The excellent performance of SATzilla was independently verified
in the 2007 SAT Competition, where our SATzilla07 solvers won three gold, one
silver and one bronze medal. In this article, we go well beyond SATzilla07 by
making the portfolio construction scalable and completely automated, and
improving it by integrating local search solvers as candidate solvers, by
predicting performance score instead of runtime, and by using hierarchical
hardness models that take into account different types of SAT instances. We
demonstrate the effectiveness of these new techniques in extensive experimental
results on data sets including instances from the most recent SAT competition.
