# T-SKM-Net: Trainable Neural Network Framework for Linear Constraint Satisfaction via Sampling Kaczmarz-Motzkin Method

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 36 references that are in the map.
- First posted on arXiv 11 Dec 2025.

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

- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [DC3: A learning method for optimization with hard constraints](https://mlsanity.com/paper/2104.12225/) (2021)
- [OSQP: An Operator Splitting Solver for Quadratic Programs](https://mlsanity.com/paper/1711.08013/) (2017)
- [Physics-Informed Generative Adversarial Networks for Stochastic Differential Equations](https://mlsanity.com/paper/1811.02033/) (2018)
- [pandapower - an Open Source Python Tool for Convenient Modeling, Analysis and Optimization of Electric Power Systems](https://mlsanity.com/paper/1709.06743/) (2017)
- [Enforcing Policy Feasibility Constraints through Differentiable Projection for Energy Optimization](https://mlsanity.com/paper/2105.08881/) (2021)
- [FSNet: Feasibility-Seeking Neural Network for Constrained Optimization with Guarantees](https://mlsanity.com/paper/2506.00362/) (2025)
- [Efficient differentiable quadratic programming layers: an ADMM approach](https://mlsanity.com/paper/2112.07464/) (2021)
- [Enforcing Hard Linear Constraints in Deep Learning Models with Decision Rules](https://mlsanity.com/paper/2505.13858/) (2025)
- [A Sampling Kaczmarz-Motzkin Algorithm for Linear Feasibility](https://mlsanity.com/paper/1605.01418/) (2016)
- [Parallel and Distributed Successive Convex Approximation Methods for Big-Data Optimization](https://mlsanity.com/paper/1805.06963/) (2018)
- [Teaching Networks to Solve Optimization Problems](https://mlsanity.com/paper/2202.04104/) (2022)
- [GLinSAT: The General Linear Satisfiability Neural Network Layer By Accelerated Gradient Descent](https://mlsanity.com/paper/2409.17500/) (2024)
- [Constructing unbiased gradient estimators with finite variance for conditional stochastic optimization](https://mlsanity.com/paper/2206.01991/) (2022)

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

- [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)

Neural network constraint satisfaction is crucial for safety-critical applications such as power system optimization, robotic path planning, and autonomous driving. However, existing constraint satisfaction methods face efficiency-applicability trade-offs, with hard constraint methods suffering from either high computational complexity or restrictive assumptions on constraint structures. The Sampling Kaczmarz-Motzkin (SKM) method is a randomized iterative algorithm for solving large-scale linear inequality systems with favorable convergence properties, but its argmax operations introduce non-differentiability, posing challenges for neural network applications. This work proposes the Trainable Sampling Kaczmarz-Motzkin Network (T-SKM-Net) framework and, for the first time, systematically integrates SKM-type methods into neural network constraint satisfaction. The framework transforms mixed constraint problems into pure inequality problems through null space transformation, employs SKM for iterative solving, and maps solutions back to the original constraint space, efficiently handling both equality and inequality constraints. We provide theoretical proof of post-processing effectiveness in expectation and end-to-end trainability guarantees based on unbiased gradient estimators, demonstrating that despite non-differentiable operations, the framework supports standard backpropagation. On the DCOPF case118 benchmark, our method achieves 4.27ms/item GPU serial forward inference with 0.0025% max optimality gap with post-processing mode and 5.25ms/item with 0.0008% max optimality gap with joint training mode, delivering over 25× speedup compared to the pandapower solver while maintaining zero constraint violations under given tolerance.