Exploiting subproblem optimization in SAT-based maxsat algorithms

DOI10.1007/s10732-015-9300-7zbMath1360.90313OpenAlexW1863234917MaRDI QIDQ525063

Joel Gabàs, Jordi Levy, Carlos Ansótegui

Publication date: 28 April 2017

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

Full work available at URL: https://doi.org/10.1007/s10732-015-9300-7

zbMATH Keywords

satisfiabilityconstraint optimizationmaximum satisfiability

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Related Items (2)

WPM3: an (in)complete algorithm for weighted partial MaxSAT ⋮ An iterative path-breaking approach with mutation and restart strategies for the MAX-SAT problem

Uses Software

• SMT-LIB
• Yices
• Sat4j
• QMaxSAT
• MiniMaxSat
• WPM2
• MaxHS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• SAT-based MaxSAT algorithms
• Boolean lexicographic optimization: algorithms \& applications
• Solving weighted CSPs with meta-constraints by reformulation into satisfiability modulo theories
• A two-phase exact algorithm for MAX-SAT and weighted MAX-SAT problems
• Iterative and core-guided maxsat solving: a survey and assessment
• A logical approach to efficient Max-SAT solving
• Improvements to Core-Guided Binary Search for MaxSAT
• Local Consistency in Weighted CSPs and Inference in Max-SAT
• Satisfiability Modulo the Theory of Costs: Foundations and Applications
• Resolution lower bounds for the weak pigeonhole principle
• New Encodings of Pseudo-Boolean Constraints into CNF
• Solving (Weighted) Partial MaxSAT through Satisfiability Testing
• Exploiting Cycle Structures in Max-SAT
• Algorithms for Weighted Boolean Optimization
• Improving Unsatisfiability-Based Algorithms for Boolean Optimization
• Metaheuristics—the metaphor exposed
• Exploiting the Power of mip Solvers in maxsat
• Unsatisfiability-based optimization in clasp
• On Solving the Partial MAX-SAT Problem
• On SAT Modulo Theories and Optimization Problems
• A Complete Calculus for Max-SAT

This page was built for publication: Exploiting subproblem optimization in SAT-based maxsat algorithms