# GLinSAT: The General Linear Satisfiability Neural Network Layer By Accelerated Gradient Descent

arXiv: https://arxiv.org/abs/2409.17500 · HTML: https://mlsanity.com/paper/2409.17500/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 47 references that are in the map.
- First posted on arXiv 26 Sep 2024.

## Builds on (most cited first, 24 of 24)

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [OptNet: Differentiable Optimization as a Layer in Neural Networks](https://mlsanity.com/paper/1703.00443/) (2017)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Differentiable Convex Optimization Layers](https://mlsanity.com/paper/1910.12430/) (2019)
- [Spectral Temporal Graph Neural Network for Multivariate Time-series Forecasting](https://mlsanity.com/paper/2103.07719/) (2021)
- [Melding the Data-Decisions Pipeline: Decision-Focused Learning for Combinatorial Optimization](https://mlsanity.com/paper/1809.05504/) (2018)
- [Differentiation of Blackbox Combinatorial Solvers](https://mlsanity.com/paper/1912.02175/) (2019)
- [SATNet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver](https://mlsanity.com/paper/1905.12149/) (2019)
- [Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs](https://mlsanity.com/paper/2006.10643/) (2020)
- [Differentiable Ranks and Sorting using Optimal Transport](https://mlsanity.com/paper/1905.11885/) (2019)
- [Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithm](https://mlsanity.com/paper/1802.04367/) (2018)
- [Learning Combinatorial Embedding Networks for Deep Graph Matching](https://mlsanity.com/paper/1904.00597/) (2019)
- [Neural Graph Matching Network: Learning Lawler's Quadratic Assignment Problem with Extension to Hypergraph and Multiple-graph Matching](https://mlsanity.com/paper/1911.11308/) (2019)
- [Deep Graph Matching via Blackbox Differentiation of Combinatorial Solvers](https://mlsanity.com/paper/2003.11657/) (2020)
- [CombOptNet: Fit the Right NP-Hard Problem by Learning Integer Programming Constraints](https://mlsanity.com/paper/2105.02343/) (2021)
- [Value constrained model-free continuous control](https://mlsanity.com/paper/1902.04623/) (2019)
- [DeepPermNet: Visual Permutation Learning](https://mlsanity.com/paper/1704.02729/) (2017)
- [RAYEN: Imposition of Hard Convex Constraints on Neural Networks](https://mlsanity.com/paper/2307.08336/) (2023)
- [Resource Constrained Deep Reinforcement Learning](https://mlsanity.com/paper/1812.00600/) (2018)
- [Computationally Efficient Safe Reinforcement Learning for Power Systems](https://mlsanity.com/paper/2110.10333/) (2021)
- [LinSATNet: The Positive Linear Satisfiability Neural Networks](https://mlsanity.com/paper/2407.13917/) (2024)
- [Better and Simpler Error Analysis of the Sinkhorn-Knopp Algorithm for Matrix Scaling](https://mlsanity.com/paper/1801.02790/) (2018)
- [Ensuring DNN Solution Feasibility for Optimization Problems with Convex Constraints and Its Application to DC Optimal Power Flow Problems](https://mlsanity.com/paper/2112.08091/) (2021)

## Built on by (most cited first, 7 of 7)

- [Pinet: Optimizing hard-constrained neural networks with orthogonal projection layers](https://mlsanity.com/paper/2508.10480/) (2025)
- [Geometric Algorithms for Neural Combinatorial Optimization with Constraints](https://mlsanity.com/paper/2510.24039/) (2025)
- [T-SKM-Net: Trainable Neural Network Framework for Linear Constraint Satisfaction via Sampling Kaczmarz-Motzkin Method](https://mlsanity.com/paper/2512.10461/) (2025)
- [DiffSlack: Learning under Nonlinear Inequality Constraints via Learnable Slack Variables](https://mlsanity.com/paper/2606.05247/) (2026)
- [Stochastic Dimension Implicit Functional Projections for Global Integral Conservation in High-Dimensional PINNs](https://mlsanity.com/paper/2603.29237/) (2026)
- [Self-Supervised Combinatorial Optimization with Constraints via Frank-Wolfe](https://mlsanity.com/paper/2609.25728/) (2026)
- [AT-SKM-Net: An Accelerated Trainable Sampling Kaczmarz-Motzkin Framework for Linear Hard-Constraint Feasibility on Dynamic Graphs](https://mlsanity.com/paper/2609.30088/) (2026)

## Abstract (arXiv)

Ensuring that the outputs of neural networks satisfy specific constraints is crucial for applying neural networks to real-life decision-making problems. In this paper, we consider making a batch of neural network outputs satisfy bounded and general linear constraints. We first reformulate the neural network output projection problem as an entropy-regularized linear programming problem. We show that such a problem can be equivalently transformed into an unconstrained convex optimization problem with Lipschitz continuous gradient according to the duality theorem. Then, based on an accelerated gradient descent algorithm with numerical performance enhancement, we present our architecture, GLinSAT, to solve the problem. To the best of our knowledge, this is the first general linear satisfiability layer in which all the operations are differentiable and matrix-factorization-free. Despite the fact that we can explicitly perform backpropagation based on automatic differentiation mechanism, we also provide an alternative approach in GLinSAT to calculate the derivatives based on implicit differentiation of the optimality condition. Experimental results on constrained traveling salesman problems, partial graph matching with outliers, predictive portfolio allocation and power system unit commitment demonstrate the advantages of GLinSAT over existing satisfiability layers. Our implementation is available at urlhttps://github.com/HunterTracer/GLinSAT.