SAT-based MaxSAT algorithms

DOI10.1016/j.artint.2013.01.002zbMath1270.68265OpenAlexW2071319337WikidataQ60512091 ScholiaQ60512091MaRDI QIDQ360042

Carlos Ansótegui, Maria Luisa Bonet, Jordi Levy

Publication date: 23 August 2013

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

Full work available at URL: http://www.sciencedirect.com/science/article/pii/S000437021300012X

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (35)

Quantified maximum satisfiability ⋮ MaxSAT by improved instance-specific algorithm configuration ⋮ Best-effort inductive logic programming via fine-grained cost-based hypothesis generation. The Inspire system at the inductive logic programming competition ⋮ Advances in WASP ⋮ Lower and Upper Bounds for Random Mimimum Satisfiability Problem ⋮ Propositional SAT Solving ⋮ A novel algorithm for Max Sat calling MOCE to order ⋮ New local search methods for partial MaxSAT ⋮ Minimal sets on propositional formulae. Problems and reductions ⋮ WPM3: an (in)complete algorithm for weighted partial MaxSAT ⋮ Understanding the complexity of axiom pinpointing in lightweight description logics ⋮ Boosting branch-and-bound MaxSAT solvers with clause learning ⋮ CHAMP: a multipass algorithm for Max Sat based on saver variables ⋮ A memetic algorithm for restoring feasibility in scheduling with limited makespan ⋮ Go-MOCE: greedy order method of conditional expectations for Max Sat ⋮ Hybrid metabolic network completion ⋮ Old techniques in new ways: clause weighting, unit propagation and hybridization for maximum satisfiability ⋮ \textit{teaspoon}: solving the curriculum-based course timetabling problems with answer set programming ⋮ Breaking Cycle Structure to Improve Lower Bound for Max-SAT ⋮ Popularity-similarity random SAT formulas ⋮ Propositional proof systems based on maximum satisfiability ⋮ CCEHC: an efficient local search algorithm for weighted partial maximum satisfiability ⋮ On the performance of MaxSAT and MinSAT solvers on 2SAT-MaxOnes ⋮ Cost-optimal constrained correlation clustering via weighted partial maximum satisfiability ⋮ Exploiting subproblem optimization in SAT-based maxsat algorithms ⋮ \(N\)-level modulo-based CNF encodings of pseudo-Boolean constraints for MaxSAT ⋮ Probabilistic characterization of random Max \(r\)-Sat ⋮ Using Merging Variables-Based Local Search to Solve Special Variants of MaxSAT Problem ⋮ The Normalized Autocorrelation Length of Random Max  $$r$$ -Sat Converges in Probability to $$(1-1/2^r)/r$$ ⋮ On the complexity of inconsistency measurement ⋮ Using the method of conditional expectations to supply an improved starting point for CCLS ⋮ RC2: an Efficient MaxSAT Solver ⋮ Clause redundancy and preprocessing in maximum satisfiability ⋮ Iterative and core-guided maxsat solving: a survey and assessment ⋮ Proofs and Certificates for Max-SAT

This page was built for publication: SAT-based MaxSAT algorithms