WPM3: an (in)complete algorithm for weighted partial MaxSAT

DOI10.1016/j.artint.2017.05.003zbMath1419.68090MaRDI QIDQ1680676

Carlos Ansótegui, Joel Gabàs

Publication date: 16 November 2017

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.artint.2017.05.003

zbMATH Keywords

optimization; SAT; MaxSAT; pseudo-Boolean constraints

Mathematics Subject Classification ID

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

Related Items

Polarity and Variable Selection Heuristics for SAT-Based Anytime MaxSAT, Open-WBO-Inc: Approximation Strategies for Incomplete Weighted MaxSAT, WPM3, SAT-based models for overlapping community detection in networks, An iterative path-breaking approach with mutation and restart strategies for the MAX-SAT problem, Old techniques in new ways: clause weighting, unit propagation and hybridization for maximum satisfiability, On preprocessing for weighted MaxSAT

Uses Software

• MiniSat
• Sat4j
• QMaxSAT
• MiniMaxSat
• WPM2
• MaxHS
• maxino
• CCLS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• MaxSAT by improved instance-specific algorithm configuration
• New local search methods for partial MaxSAT
• SAT-based MaxSAT algorithms
• Curriculum-based course timetabling with SAT and MaxSAT
• Exploiting subproblem optimization in SAT-based maxsat algorithms
• Cardinality networks: a theoretical and empirical study
• Resolution for Max-SAT
• Iterative and core-guided maxsat solving: a survey and assessment
• Improvements to Core-Guided Binary Search for MaxSAT
• Efficient and Accurate Haplotype Inference by Combining Parsimony and Pedigree Information
• CCLS: An Efficient Local Search Algorithm for Weighted Maximum Satisfiability
• Towards an Optimal CNF Encoding of Boolean Cardinality Constraints
• 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
• Optimal Protein Structure Alignment Using Maximum Cliques
• Exploiting the Power of mip Solvers in maxsat
• Theory and Applications of Satisfiability Testing
• Principles and Practice of Constraint Programming – CP 2003
• A ``logic-constrained knapsack formulation and a tabu algorithm for the daily photograph scheduling of an earth observation satellite