Exact Max-SAT solvers for over-constrained problems

DOI10.1007/s10732-006-7234-9zbMath1100.68107MaRDI QIDQ2506236

Felip Manyà, Josep Argelich

Publication date: 28 September 2006

Published in: Journal of Heuristics (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/10459.1/57408

zbMATH Keywords

Soft constraints; Max-SAT; Solvers

Mathematics Subject Classification ID

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

68P05: Data structures

Related Items

MaxSAT by improved instance-specific algorithm configuration, An improved algorithm for the \((n, 3)\)-MaxSAT problem: asking branchings to satisfy the clauses, Reoptimization of minimum latency problem revisited: don't panic when asked to revisit the route after local modifications, Modelling Max-CSP as Partial Max-SAT, A Preprocessor for Max-SAT Solvers, On Inconsistent Clause-Subsets for Max-SAT Solving

Uses Software

• MaxSolver
• Chaff

Cites Work

• Unnamed Item
• Unnamed Item
• A two-phase exact algorithm for MAX-SAT and weighted MAX-SAT problems
• Current approaches for solving over-constrained problems
• Partition-based lower bound for Max-CSP
• MaxSolver: An efficient exact algorithm for (weighted) maximum satisfiability
• On the parallel complexity of discrete relaxation in constraint satisfaction networks
• 2 -Way vs.d -Way Branching for CSP
• Exploiting Unit Propagation to Compute Lower Bounds in Branch and Bound Max-SAT Solvers
• A machine program for theorem-proving
• Theory and Applications of Satisfiability Testing
• Principles and Practice of Constraint Programming – CP 2003
• Faster exact algorithms for hard problems: A parameterized point of view