Optimizing with minimum satisfiability

DOI10.1016/j.artint.2012.05.004zbMath1251.68209OpenAlexW2045794350MaRDI QIDQ1761303

Felip Manyà, Chu-Min Li, Laurent Simon, Zhu Zhu

Publication date: 15 November 2012

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

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

zbMATH Keywords

combinatorial optimizationbranch-and-boundsatisfiabilityMaxSATMinSAT

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (11)

Lower and Upper Bounds for Random Mimimum Satisfiability Problem ⋮ A primal-dual approximation algorithm for \textsc{minsat} ⋮ Minimal sets on propositional formulae. Problems and reductions ⋮ Incremental Upper Bound for the Maximum Clique Problem ⋮ A non-clausal tableau calculus for \textsc{MinSat} ⋮ On the performance of MaxSAT and MinSAT solvers on 2SAT-MaxOnes ⋮ A new upper bound for the maximum weight clique problem ⋮ Iterated local search with Trellis-neighborhood for the partial Latin square extension problem ⋮ Allocating limited resources to protect a massive number of targets using a game theoretic model ⋮ Voting on multi-issue domains with conditionally lexicographic preferences ⋮ Set-weighted games and their application to the cover problem

Uses Software

• MaxCliqueDyn

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Resolution-based lower bounds in MaxSAT
• On approximation algorithms for the minimum satisfiability problem
• Approximating MIN 2-SAT and MIN 3-SAT
• Exploiting Unit Propagation to Compute Lower Bounds in Branch and Bound Max-SAT Solvers
• The Minimum Satisfiability Problem
• Exact MinSAT Solving

This page was built for publication: Optimizing with minimum satisfiability