Hierarchical Hardness Models for SAT

DOI10.1007/978-3-540-74970-7_49MaRDI QIDQ3523084zbMATH OpenOpenAlexFDO

Authors Lin Xu, Holger H. Hoos, Kevin Leyton-Brown

Publication date 2 September 2008

Published in Principles and Practice of Constraint Programming – CP 2007 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-74970-7_49

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• Principles and Practice of Constraint Programming – CP 2004
• On SAT instance classes and a method for reliable performance experiments with SAT solvers
• Empirical hardness models, methodology and a case study on combinatorial auctions
• scientific article; zbMATH DE number 1113991
• SATzilla: portfolio-based algorithm selection for SAT

Cites work

• Generating hard satisfiability problems
• Heavy-tailed phenomena in satisfiability and constraint satisfaction problems
• scientific article; zbMATH DE number 67483 (Why is no real title available?)
• March\_dl: adding adaptive heuristics and a new branching strategy
• Pattern recognition and machine learning.
• Performance Prediction and Automated Tuning of Randomized and Parametric Algorithms
• Principles and Practice of Constraint Programming – CP 2004
• SATO: An efficient propositional prover
• SATzilla: portfolio-based algorithm selection for SAT
• Theory and Applications of Satisfiability Testing
• Theory and Applications of Satisfiability Testing

Cited in

(11)

• A self-adaptive multi-engine solver for quantified Boolean formulas
• Towards a reference model for timetabling and rostering
• On SAT instance classes and a method for reliable performance experiments with SAT solvers
• A Bayesian approach to tackling hard computational problems. (Preliminary report)
• ASlib: a benchmark library for algorithm selection
• Empirical hardness models, methodology and a case study on combinatorial auctions
• aspeed: solver scheduling via answer set programming
• Algorithm runtime prediction: methods \& evaluation
• Principles and Practice of Constraint Programming – CP 2004
• Evolutionary Computation in Combinatorial Optimization
• Practical performance models of algorithms in evolutionary program induction and other domains

This page was built for publication: Hierarchical Hardness Models for SAT

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3523084)