torchmSAT: A GPU-Accelerated Approximation To The Maximum Satisfiability Problem
CoRR(2024)
摘要
The remarkable achievements of machine learning techniques in analyzing
discrete structures have drawn significant attention towards their integration
into combinatorial optimization algorithms. Typically, these methodologies
improve existing solvers by injecting learned models within the solving loop to
enhance the efficiency of the search process. In this work, we derive a single
differentiable function capable of approximating solutions for the Maximum
Satisfiability Problem (MaxSAT). Then, we present a novel neural network
architecture to model our differentiable function, and progressively solve
MaxSAT using backpropagation. This approach eliminates the need for labeled
data or a neural network training phase, as the training process functions as
the solving algorithm. Additionally, we leverage the computational power of
GPUs to accelerate these computations. Experimental results on challenging
MaxSAT instances show that our proposed methodology outperforms two existing
MaxSAT solvers, and is on par with another in terms of solution cost, without
necessitating any training or access to an underlying SAT solver. Given that
numerous NP-hard problems can be reduced to MaxSAT, our novel technique paves
the way for a new generation of solvers poised to benefit from neural network
GPU acceleration.
更多查看译文
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要