mlsanityData to 14 Oct 2026

LinSATNet: The Positive Linear Satisfiability Neural Networks

arXiv 2407.13917 ↗First posted 18 Jul 2024cs.AI math.OCcited by 16

Not on the map. Why?

Abstract (arXiv)

Encoding constraints into neural networks is attractive. This paper studies how to introduce the popular positive linear satisfiability to neural networks. We propose the first differentiable satisfiability layer based on an extension of the classic Sinkhorn algorithm for jointly encoding multiple sets of marginal distributions. We further theoretically characterize the convergence property of the Sinkhorn algorithm for multiple marginals. In contrast to the sequential decision e.g. reinforcement learning-based solvers, we showcase our technique in solving constrained (specifically satisfiability) problems by one-shot neural networks, including i) a neural routing solver learned without supervision of optimal solutions; ii) a partial graph matching network handling graphs with unmatchable outliers on both sides; iii) a predictive network for financial portfolios with continuous constraints. To our knowledge, there exists no one-shot neural solver for these scenarios when they are formulated as satisfiability problems. Source code is available at https://github.com/Thinklab-SJTU/LinSATNet

Key facts. Cited by 16 papers in the map (data through 14 Oct 2026). Builds on 32 of its 63 references that are in the map. First posted on arXiv 18 Jul 2024.

Builds on

32 of 63 references.

References · 32

  1. 2017Attention Is All You Needcited by 60,361
  2. 2014Very Deep Convolutional Networks for Large-Scale Image Recognitioncited by 15,364
  3. 2013Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distancescited by 2,316
  4. 2015Pointer Networkscited by 895
  5. 2018Attention, Learn to Solve Routing Problems!cited by 656
  6. 2018Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizoncited by 623
  7. 2017OptNet: Differentiable Optimization as a Layer in Neural Networkscited by 599
  8. 2019Differentiable Convex Optimization Layerscited by 465
  9. 2021Spectral Temporal Graph Neural Network for Multivariate Time-series Forecastingcited by 299
  10. 2019An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problemcited by 269
  11. 2019Differentiation of Blackbox Combinatorial Solverscited by 226
  12. 2017Near-linear time approximation algorithms for optimal transport via Sinkhorn iterationcited by 223
20 more
  1. 2018Learning a SAT Solver from Single-Bit Supervisioncited by 200
  2. 2019SATNet: Bridging deep learning and logical reasoning using a differentiable satisfiability solvercited by 173
  3. 2017SplineCNN: Fast Geometric Deep Learning with Continuous B-Spline Kernelscited by 161
  4. 2020Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphscited by 115
  5. 2019Differentiable Ranks and Sorting using Optimal Transportcited by 113
  6. 2019Learning Combinatorial Embedding Networks for Deep Graph Matchingcited by 99
  7. 2021Matrix Encoding Networks for Neural Combinatorial Optimizationcited by 91
  8. 2019Neural Graph Matching Network: Learning Lawler's Quadratic Assignment Problem with Extension to Hypergraph and Multiple-graph Matchingcited by 84
  9. 2020Deep Graph Matching via Blackbox Differentiation of Combinatorial Solverscited by 81
  10. 2021CombOptNet: Fit the Right NP-Hard Problem by Learning Integer Programming Constraintscited by 49
  11. 2014Multi-marginal optimal transport: theory and applicationscited by 41
  12. 2017DeepPermNet: Visual Permutation Learningcited by 32
  13. 2021Goal-Aware Neural SAT Solvercited by 28
  14. 2021A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphscited by 26
  15. 2020Combinatorial Learning of Graph Edit Distance via Dynamic Embeddingcited by 25
  16. 2022Machine Learning Methods in Solving the Boolean Satisfiability Problemcited by 22
  17. 2018Better and Simpler Error Analysis of the Sinkhorn-Knopp Algorithm for Matrix Scalingcited by 14
  18. 2023HardSATGEN: Understanding the Difficulty of Hard SAT Formula Generation and A Strong Structure-Hardness-Aware Baselinecited by 12
  19. 2020Revocable Deep Reinforcement Learning with Affinity Regularization for Outlier-Robust Graph Matchingcited by 11
  20. 2014Using Optimization to Solve Positive LPs Faster in Parallelcited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 3; 2025: 6; 2026: 7.

16 papers.

Sort:

  1. 2024HardNet: Hard-Constrained Neural Networks with Universal Approximation Guaranteescited by 31
  2. 2025Pinet: Optimizing hard-constrained neural networks with orthogonal projection layerscited by 19
  3. 2025ENFORCE: Nonlinear Constrained Learning with Adaptive-depth Neural Projectioncited by 17
  4. 2024GLinSAT: The General Linear Satisfiability Neural Network Layer By Accelerated Gradient Descentcited by 7
  5. 2025Learning-Guided Rolling Horizon Optimization for Long-Horizon Flexible Job-Shop Schedulingcited by 7
  6. 2025Geometric Algorithms for Neural Combinatorial Optimization with Constraintscited by 4
  7. 2024Learning to Solve Combinatorial Optimization under Positive Linear Constraints via Non-Autoregressive Neural Networkscited by 2
  8. 2025Enforcing convex constraints in Graph Neural Networkscited by 2
  9. 2025Deep Generative Models with Hard Linear Equality Constraintscited by 1
  10. 2026DiffSlack: Learning under Nonlinear Inequality Constraints via Learnable Slack Variablescited by 1
  11. 2026Stochastic Dimension Implicit Functional Projections for Global Integral Conservation in High-Dimensional PINNscited by 0
  12. 2026Efficient and provably convergent end-to-end training of deep neural networks with linear constraintscited by 0
4 more
  1. 2026N(CO)2: Neural Combinatorial Optimization with Chance Constraints to Solve Stochastic Orienteeringcited by 0
  2. 2026GLACIER: Rethinking Mass Spectrum Prediction as an Object Detection Problemcited by 0
  3. 2026Self-Supervised Combinatorial Optimization with Constraints via Frank-Wolfecited by 0
  4. 2026AT-SKM-Net: An Accelerated Trainable Sampling Kaczmarz-Motzkin Framework for Linear Hard-Constraint Feasibility on Dynamic Graphscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Neural Approaches to SAT Solving: Design Choices and Interpretability
  2. 2025Learning from Algorithm Feedback: One-Shot SAT Solver Guidance with GNNs
  3. 2023Learning Reliable Logical Rules with SATNet
  4. 2026Hypergraph Neural Networks Accelerate MUS Enumeration
  5. 2022Learning Symmetric Rules with SATNet
  6. 2022Denoising Diffusion for Sampling SAT Solutions
  7. 2023Assessing SATNet's Ability to Solve the Symbol Grounding Problem
  8. 2026Streamlined Constraint Reasoning via CNN Pattern Recognition on Enumerated Solutions