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 practice. This paper presents a new algorithm for computing approximate solutions in ${\Theta(N})$ for the Maximum Exact 3-Satisfiability (MAX-E-$3$-SAT) problem by using deep learning methodology. This methodology allows us to create a learning algorithm able to fix Boolean variables by using local information obtained by the Survey Propagation algorithm. By performing an accurate analysis, on random CNF instances of the MAX-E-$3$-SAT with several Boolean variables, we show that this new algorithm, avoiding any decimation strategy, can build assignments better than a random one, even if the convergence of the messages is not found. Although this algorithm is not competitive with state-of-the-art Maximum Satisfiability (MAX-SAT) solvers, it can solve substantially larger and more complicated problems than it ever saw during training.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
CPR for CSPs: A Probabilistic Relaxation of Constraint Propagation
This paper proposes constraint propagation relaxation (CPR), a probabilistic approach to classical constraint propagation that provides another view on the whole parametric family of survey propagation algorithms SP(`…
SurveyPairwise Constraint Propagation: A Survey
As one of the most important types of (weaker) supervised information in machine learning and pattern recognition, pairwise constraint, which specifies whether a pair of data points occur together, has recently received …
SurveyRelaxed 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 …
SurveyPerturbed Message Passing for Constraint Satisfaction Problems
We introduce an efficient message passing scheme for solving Constraint Satisfaction Problems (CSPs), which uses stochastic perturbation of Belief Propagation (BP) and Survey Propagation (SP) messages to bypass decimatio…
SurveyComprehensive Survey of Complex-Valued Neural Networks: Insights into Backpropagation and Activation Functions
Artificial neural networks (ANNs), particularly those employing deep learning models, have found widespread application in fields such as computer vision, signal processing, and wireless communications, where complex num…
Survey