Relaxed Survey Propagation for The Weighted Maximum Satisfiability Problem
The survey propagation (SP) algorithm has been shown to work well on large instances of the random 3-SAT problem near its phase transition. It was shown that SP estimates marginals over covers that represent clusters of solutions. The SP-y algorithm generalizes SP to work on the maximum satisfiability (Max-SAT) problem, but the cover interpretation of SP does not generalize to SP-y. In this paper, we formulate the relaxed survey propagation (RSP) algorithm, which extends the SP algorithm to apply to the weighted Max-SAT problem. We show that RSP has an interpretation of estimating marginals over covers violating a set of clauses with minimal weight. This naturally generalizes the cover interpretation of SP. Empirically, we show that RSP outperforms SP-y and other state-of-the-art Max-SAT solvers on random Max-SAT instances. RSP also outperforms state-of-the-art weighted Max-SAT solvers on random weighted Max-SAT instances.
Code (0)
등록된 구현이 없습니다.
Tasks
SurveySimilar Papers 제목 키워드 기반
Learning from Survey Propagation: a Neural Network for MAX-E-$3$-SAT
Many natural optimization problems are NP-hard, which implies that they are probably hard to solve exactly in the worst-case. However, it suffices to get reasonably good solutions for all (or even most) instances in prac…
Fuzzy Maximum Satisfiability
In this paper, we extend the Maximum Satisfiability (MaxSAT) problem to {\L}ukasiewicz logic. The MaxSAT problem for a set of formulae {\Phi} is the problem of finding an assignment to the variables in {\Phi} that satisf…
Approximating the Backbone in the Weighted Maximum Satisfiability Problem
The weighted Maximum Satisfiability problem (weighted MAX-SAT) is a NP-hard problem with numerous applications arising in artificial intelligence. As an efficient tool for heuristic design, the backbone has been applied …
HyperSAT: Unsupervised Hypergraph Neural Networks for Weighted MaxSAT Problems
Graph neural networks (GNNs) have shown promising performance in solving both Boolean satisfiability (SAT) and Maximum Satisfiability (MaxSAT) problems due to their ability to efficiently model and capture the structural…
Belief Propagation for Maximum Coverage on Weighted Bipartite Graph and Application to Text Summarization
We study text summarization from the viewpoint of maximum coverage problem. In graph theory, the task of text summarization is regarded as maximum coverage problem on bipartite graph with weighted nodes. In recent study,…
Text Summarization