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.