Learning from Survey Propagation: a Neural Network for MAX-E-$3$-SAT
- URL: http://arxiv.org/abs/2012.06344v2
- Date: Sun, 14 Feb 2021 09:22:57 GMT
- Title: Learning from Survey Propagation: a Neural Network for MAX-E-$3$-SAT
- Authors: Raffaele Marino
- Abstract summary: This paper presents a new algorithm for computing approximate solutions in $Theta(N)$ for the Maximum Exact 3-Satisfiability (MAX-E-$3$-SAT) problem.
- Score: 0.0
- License: http://creativecommons.org/publicdomain/zero/1.0/
- Abstract: 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.
Related papers
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP)
We generalize the SDP-inspired quantum algorithm to sum-of-squares.
Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
arXiv Detail & Related papers (2024-08-14T19:04:13Z) - torchmSAT: A GPU-Accelerated Approximation To The Maximum Satisfiability
Problem [1.5850859526672516]
We derive a single differentiable function capable of approximating solutions for the Maximum Satisfiability Problem (MaxSAT)
We present a novel neural network architecture to model our differentiable function, and progressively solve MaxSAT using backpropagation.
arXiv Detail & Related papers (2024-02-06T02:33:00Z) - Decomposing Hard SAT Instances with Metaheuristic Optimization [52.03315747221343]
We introduce the notion of decomposition hardness (d-hardness)
We show that the d-hardness expresses an estimate of the hardness of $C$ w.r.t.
arXiv Detail & Related papers (2023-12-16T12:44:36Z) - Solving a Class of Non-Convex Minimax Optimization in Federated Learning [84.98927714326908]
The minimax problems arise throughout machine learning applications, ranging from machine learning training to large-scale learning.
We propose a class of algorithms for non minimax problems (emphi) that reduce complexity to $varepsilon-6)$.
We prove that FedSGDA-M has the best sample complexity of $O(kappa2-3)$ and the best-known communication of $O(kappa2-3)$.
arXiv Detail & Related papers (2023-10-05T15:48:41Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss.
Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
arXiv Detail & Related papers (2023-07-24T14:37:22Z) - Asymptotic Instance-Optimal Algorithms for Interactive Decision Making [35.76184529520015]
In this paper, we design the first instance-optimal algorithm for general interactive decision making problems with finite number of decisions under mild conditions.
Our results, instantiated on concrete problems, recover the classical gap-dependent bounds for multi-armed bandits and prior works on linear bandits.
arXiv Detail & Related papers (2022-06-06T02:56:10Z) - Choosing the Right Algorithm With Hints From Complexity Theory [16.33500498939925]
We show that the Metropolis algorithm is clearly the best of all algorithms regarded for reasonable problem sizes.
An artificial algorithm of this type having an $O(n log n)$ runtime leads to the result that the significance-based compact genetic algorithm (sig-cGA) can solve the DLB problem in time $O(n log n)$ with high probability.
arXiv Detail & Related papers (2021-09-14T11:12:32Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
We propose a new algorithm for the min-player against smooth algorithms deployed by an adversary.
Our algorithm is guaranteed to make monotonic progress having no limit cycles, and to find an appropriate number of gradient ascents.
arXiv Detail & Related papers (2021-06-02T22:03:36Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
This paper investigates the classical integer least-squares problem which estimates signals integer from linear models.
The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning.
We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
arXiv Detail & Related papers (2021-01-07T08:00:02Z) - Curriculum learning for multilevel budgeted combinatorial problems [7.804994311050265]
Multilevel optimization problems are their generalization, encompassing situations with multiple players taking decisions sequentially.
We devise a value-based method to learn to solve multilevel budgeted problems involving two players in a zero-sum game over a graph.
Our framework is based on a simple curriculum: if an agent knows how to estimate the value of instances with budgets up to $B$, then solving instances with budget $B+1$ can be done in time regardless of the direction of every possible afterstate.
arXiv Detail & Related papers (2020-07-07T01:09:37Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.