Research map / Optimization / Optimizers
GLinSAT: The General Linear Satisfiability Neural Network Layer By Accelerated Gradient Descent
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes GLinSAT, a GPU-friendly, matrix-factorization-free neural network layer that enforces general bounded linear constraints by solving an entropy-regularized LP via its unconstrained dual with accelerated gradient descent.
Problem
Making batches of neural network outputs satisfy bounded general linear (including equality and negative-coefficient) constraints in a differentiable and GPU-efficient way.
Approach
Reformulate the output projection as an entropy-regularized LP whose Lagrange dual is an unconstrained convex problem with Lipschitz gradient, solved by adaptive primal-dual accelerated gradient descent using only matrix-vector products; backward pass via implicit differentiation with conjugate gradient.
Key results
- GLinSAT-Dense-Implicit uses about 13 MB projection GPU memory and 0.143 s backprop time on TSP-StartEnd versus 14305 MB and 0.929 s for OptNet, with the fastest overall time.
- On unit commitment, GLinSAT with 1/theta <= 0.0005 reaches 100% feasibility ratio while sigmoid output yields 0% feasible solutions.
- On portfolio allocation, GLinSAT achieves Sharpe ratio 2.608 at 1/theta=0.01, versus 2.409 for LinSAT.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use GLinSAT-Dense-Implicit instead of LinSAT-Sparse-500 | TSP-StartEnd with beam search · TSP-StartEnd, beam search (1/θ = 10⁻¹) | mean tour length: 3.818 -> 3.811 | Helped |
| Use GLinSAT-Dense-Implicit instead of LinSAT-Dense-500 | TSP-Priority with beam search · TSP-Priority, beam search (1/θ = 10⁻¹) | mean tour length: 3.947 -> 3.927 | Helped |
| Use GLinSAT-Dense-Implicit instead of LinSAT-Dense-100 | TSP-StartEnd training batch · TSP-StartEnd training batch | projection time: 0.278 -> 0.306 | Hurt |
| Use implicit rather than explicit backpropagation (ablation) | GLinSAT dense on TSP-StartEnd · TSP-StartEnd training batch | backpropagation time: 0.240 -> 0.143 | Helped |
| Use implicit rather than explicit backpropagation (ablation) | GLinSAT dense on TSP-StartEnd · TSP-StartEnd training batch | backpropagation GPU memory: 4.868 -> 53.23 | Hurt |
| Use GLinSAT-Dense-Explicit instead of LinSAT-Sparse-100 | partial graph matching · Pascal VOC Keypoint, unfiltered, 1/θ = 10⁻² | mean F1: 0.618 -> 0.620 | Helped |
| Use GLinSAT-Dense-Explicit instead of OptNet | predictive portfolio allocation · Portfolio allocation, 1/θ = 10⁻¹ | mean Sharpe ratio: 2.553 -> 2.535 | Hurt |
| Use GLinSAT-Dense-Explicit instead of CvxpyLayers | predictive portfolio allocation · Portfolio allocation, 1/θ = 10⁻² | mean Sharpe ratio: 2.600 -> 2.608 | Helped |
| Decrease 1/θ from 0.01 to 0.0005 (ablation) | GLinSAT-Sparse-Implicit · Power system unit commitment validation | feasibility ratio: 86.23% -> 100% | Helped |
| Replace the satisfiability layer with sigmoid (ablation) | unit commitment training and validation · Power system unit commitment validation | feasibility ratio: 100% -> 0% | Hurt |
Surprising findings
- LinSAT with 100 iterations produces poor rounded TSP solutions (15.3% feasibility), and raising its iteration cap to 500 still underperforms GLinSAT.
- Sigmoid output layers yield zero feasible unit commitment solutions even after fixing and solving the continuous problem.
Limitations
- Only handles bounded variables; one-sided or unbounded variables need implicit bound computation.
- Only linear constraints supported; cone constraints are future work.
- Baselines CvxpyLayers and OptNet were only run for one epoch because training was too slow to finish.
Experimental setup
Datasets: TSP dataset Pascal VOC Keypoint with Berkeley annotations predictive portfolio allocation dataset one-year provincial power system load data
Benchmarks: constrained TSP (TSP-StartEnd, TSP-Priority) partial graph matching with outliers (Pascal VOC) predictive portfolio allocation power system unit commitment
Metrics: GPU memory solution time mean tour length feasibility ratio F1 score Sharpe ratio average gap
Baselines: CvxpyLayers OptNet LinSAT Sigmoid Gurobi-LP
Builds on: LinSAT Sinkhorn algorithm OptNet CvxpyLayers adaptive primal-dual accelerated gradient descent
Closest papers by meaning
- LinSATNet: The Positive Linear Satisfiability Neural Networks (ICML 2023 · similarity 0.87)
- On the Power of Small-size Graph Neural Networks for Linear Programming (NeurIPS 2024 · similarity 0.86)
- Expressive Power of Graph Neural Networks for (Mixed-Integer) Quadratic Programs (ICML 2025 · similarity 0.86)
- Learning Generalized Linear Programming Value Functions (NeurIPS 2024 · similarity 0.85)
- Learning Initial Basis Selection for Linear Programming via Duality-Inspired Tripartite Graph Representation and Comprehensive Supervision (ICML 2025 · similarity 0.84)
- Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Faster (ICML 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.