Thu, 21 Aug 2008 17:28:14 BST CiteULike: sdvillal Hoos http://www.citeulike.org/user/sdvillal/author/Hoos CiteULike.org en-gb Copyright © 2004-2008 citeulike.org http://www.citeulike.org/user/sdvillal/article/2793881 <i>Principles and Practice of Constraint Programming (2007), pp. 712-727.</i><br /><br />It has been widely observed that there is no "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 a per-instance solver portfolio for SAT, SATzilla-07, which uses so-called empirical hardness models to choose among its constituent solvers. We leverage new model-building techniques such as censored sampling and hierarchical hardness models, and demonstrate the effectiveness of our techniques by building a portfolio of state-of-the-art SAT solvers and evaluating it on several widely-studied SAT data sets. Overall, we show that our portfolio significantly outperforms its constituent algorithms on every data set. Our approach has also proven itself to be effective in practice: in the 2007 SAT competition, SATzilla-07 won three gold medals, one silver, and one bronze; it is available online at http://www.cs.ubc.ca/labs/beta/Projects/SATzilla . The Design and Analysis of an Algorithm Portfolio for SAT Lin Xu Frank Hutter Holger Hoos Kevin Leyton-Brown doi:10.1007/978-3-540-74970-7_50 Principles and Practice of Constraint Programming (2007), pp. 712-727. 2008-05-13T08:11:57-00:00 2007 Principles and Practice of Constraint Programming 712 727 algorithm-portfolio data-mining-general meta-learning sat