SATzilla
SATzilla: portfolio-based algorithm selection for SAT. 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.
Keywords for this software
References in zbMATH (referenced in 86 articles )
Showing results 1 to 20 of 86.
Sorted by year (- Ábrahám, Erika; Davenport, James H.; England, Matthew; Kremer, Gereon: Deciding the consistency of non-linear real arithmetic constraints with a conflict driven search using cylindrical algebraic coverings (2021)
- Dantas, Augusto; Pozo, Aurora: On the use of fitness landscape features in meta-learning based algorithm selection for the quadratic assignment problem (2020)
- González, Jaime E.; Cire, Andre A.; Lodi, Andrea; Rousseau, Louis-Martin: Integrated integer programming and decision diagram search tree with an application to the maximum independent set problem (2020)
- England, Matthew; Florescu, Dorian: Comparing machine learning models to choose the variable ordering for cylindrical algebraic decomposition (2019)
- Lindauer, Marius; van Rijn, Jan N.; Kotthoff, Lars: The algorithm selection competitions 2015 and 2017 (2019)
- Martínez-Plumed, Fernando; Prudêncio, Ricardo B. C.; Martínez-Usó, Adolfo; Hernández-Orallo, José: Item response theory in AI: analysing machine learning classifiers at the instance level (2019)
- Ngoko, Yanik; Cérin, Christophe; Trystram, Denis: Solving SAT in a distributed cloud: a portfolio approach (2019)
- Nikolić, Mladen; Marinković, Vesna; Kovács, Zoltán; Janičić, Predrag: Portfolio theorem proving and prover runtime prediction for geometry (2019)
- Cerutti, Federico; Vallati, Mauro; Giacomin, Massimiliano: On the impact of configuration on abstract argumentation automated reasoning (2018)
- Eggensperger, Katharina; Lindauer, Marius; Hoos, Holger H.; Hutter, Frank; Leyton-Brown, Kevin: Efficient benchmarking of algorithm configurators via model-based surrogates (2018)
- England, Matthew: Machine learning for mathematical software (2018)
- Gent, Ian P.; Miguel, Ian; Nightingale, Peter; McCreesh, Ciaran; Prosser, Patrick; Moore, Neil C. A.; Unsworth, Chris: A review of literature on parallel constraint solving (2018)
- Gnad, Daniel; Hoffmann, Jörg: Star-topology decoupled state space search (2018)
- Malone, Brandon; Kangas, Kustaa; Järvisalo, Matti; Koivisto, Mikko; Myllymäki, Petri: Empirical hardness of finding optimal Bayesian network structures: algorithm selection and runtime prediction (2018)
- Marques-Silva, Joao; Malik, Sharad: Propositional SAT solving (2018)
- Olier, Ivan; Sadawi, Noureddin; Bickerton, G. Richard; Vanschoren, Joaquin; Grosan, Crina; Soldatova, Larisa; King, Ross D.: Meta-QSAR: a large-scale application of meta-learning to drug design and discovery (2018)
- Souravlias, Dimitris; Parsopoulos, Konstantinos E.: On the design of metaheuristics-based algorithm portfolios (2018)
- Wistuba, Martin; Schilling, Nicolas; Schmidt-Thieme, Lars: Scalable Gaussian process-based transfer surrogates for hyperparameter optimization (2018)
- Yin, Yue; Vorobeychik, Yevgeniy; An, Bo; Hazon, Noam: Optimal defense against election control by deleting voter groups (2018)
- Demyanova, Yulia; Pani, Thomas; Veith, Helmut; Zuleger, Florian: Empirical software metrics for benchmarking of verification tools (2017)