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.

利用机器学习技术将离散结构与组合优化算法集成，提出一种能够近似求解最大满足性问题的可微函数，设计了一种新颖的神经网络结构并借助后向传播逐步求解问题，通过利用GPU进行计算加速，论文实验证明这种方法在挑战性的最大满足性问题上优于两种现有求解器，并与另一种求解器在解决成本方面相当，而无需进行训练或使用底层SAT求解器，为基于神经网络GPU加速的新一代求解器铺平了道路。

torchmSAT：一个GPU加速的最大可满足性问题的近似算法