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

DOI10.1016/j.artint.2017.05.003zbMath1419.68090OpenAlexW2621108739MaRDI 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

optimizationSATMaxSATpseudo-Boolean constraints

Mathematics Subject Classification ID

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

Related Items (8)

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

Uses Software

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

Cites Work

• 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
• Unsatisfiability-based optimization in clasp
• 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

This page was built for publication: WPM3: an (in)complete algorithm for weighted partial MaxSAT