GLinSAT: The General Linear Satisfiability Neural Network Layer By Accelerated Gradient Descent
This addresses the need for reliable constraint satisfaction in neural networks for real-life decision-making applications, offering a novel layer that is more general and efficient than existing methods.
The paper tackles the problem of ensuring neural network outputs satisfy bounded general linear constraints by introducing GLinSAT, a differentiable and matrix-factorization-free layer that reformulates the projection as an entropy-regularized linear programming problem and solves it via accelerated gradient descent, demonstrating advantages in tasks like constrained traveling salesman problems and predictive portfolio allocation.
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 \url{https://github.com/HunterTracer/GLinSAT}.