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

Summary

This paper presents a new approach to enforce constraints on the output of neural networks. Termed **G**LinSAT, this paper extends the application scope of LinSAT from positive linear constraints to general linear constraints. The authors also adopt ideas from OptNet/Cvxpylayers to derive implicit gradients in order to save GPU memory. Experiment study on all 3 experiments involved in LinSAT paper and one more case study with negative constraint terms show the proposed method works as expected to enforce constraints, while at the same time, offering better efficiency in GPU memory and (in many cases) running time.

Strengths

* Enforcing constraints to the output of neural networks is an important research direction given the fact that deep neural networks are being extended from "traditional" classification and regression tasks to more complicated real-world decision-making with complicated constraints. * The proposed approach seems technically sound. It was well-grounded with existing work (including LinSAT and OptNet) and the derivation of Lagrange duals and adoption of ADPAGD sounds novel and interesting. * The experiment study shows that the proposed GLinSAT is able to encode the constraint as expected, reaching similar (and marginally better) accuracy than LinSAT. At the same time, it is more GPU memory efficient, which is important for scaling up the applications.

Weaknesses

* The major drawback of GLinSAT over LinSAT is that its inference time is longer if LinSAT is set with its default 100 iterations. It will be helpful for the readers if there is a "discussion" section about what are the practical tips and suggestions for choosing the method for encoding constraints.

Questions

* In the discussion of the limitation of LinSAT, the authors mentioned the bin packing problem as an example. Can you elaborate on why the bin-packing constraint has negative components? * Can we derive a similar form by maximizing $\mathbf{c}^\top\mathbf{x}$? I think it is more intuitive that larger values are preserved to be larger after an activation layer (like GLinSAT). * How to compute $\partial x/\partial y$ in Eq (11)? * Please make sure the code is released and easily accessible to the research community if this paper is accepted.

Rating

8

Confidence

4

Soundness

4

Presentation

3

Contribution

4

Limitations

N/A

Summary

The paper introduces "GLinSAT," a novel neural network layer designed to enforce general linear and bounded constraints on neural network outputs using a differentiable approach. The method leverages entropy-regularized linear programming, transforming it into an unconstrained convex optimization problem that avoids matrix factorization and is efficiently solvable on GPUs using accelerated gradient descent. The authors present experimental results that demonstrate the effectiveness of GLinSAT compared to existing solutions across several constrained decision-making applications.

Strengths

1. The paper addresses the challenge of imposing general linear constraints on neural network outputs in a differentiable manner. The approach of using entropy-regularized linear programming and transforming it into an unconstrained optimization problem is novel and technically sound. 2. The reformulation from a projection problem to an unconstrained optimization problem not only ensures differentiability but also boosts computational efficiency, as demonstrated in the forward and backward processes through dual formulation-based optimization and implicit differentiation. 3. The experiments cover a diverse set of applications, including the traveling salesman problem, graph matching, portfolio allocation, and power system unit commitment. The proposed GLinSAT outperforms several baselines over those problems in terms of constraint satisfaction and computational efficiency.

Weaknesses

1. Besides differentiable layer-related works, the paper could benefit from a more extensive review of other works about NN feasibility over linear constraints, such as [1], [2], and [3]. 2. The motivation for using a dot product in the objective function (Eq. 3) as opposed to a standard L2/L1 norm minimization for projection problems is unclear. Clarification on the rationale behind this choice, its advantages, or specific scenarios where it is particularly beneficial would be valuable. Additionally, is dot-product-based projection the only one that admits the entropy-regularized formulation and the unconstrained dual problem? 3. The comparison between the entropy-regularized and the unregularized projection problems could be more explicitly detailed, especially how the optimality gap between the two problems is affected by $\theta$. [1] "Tordesillas, J., How, J. P., & Hutter, M. (2023). Rayen: Imposition of hard convex constraints on neural networks. arXiv preprint arXiv:2307.08336.", [2] "Zhao, T., Pan, X., Chen, M., & Low, S. (2023). Ensuring DNN solution feasibility for optimization problems with linear constraints. In The Eleventh International Conference on Learning Representations." [3] "Tabas, D., & Zhang, B. (2022, June). Computationally efficient safe reinforcement learning for power systems. In 2022 American Control Conference (ACC) (pp. 3303-3310). IEEE."

Questions

1. For L2 projection layer, the projection distance will be no larger than the approximation error; thus, the universal approximation ability of NN+L2-projection will be maintained. Meanwhile, with the dot-product-based projection layer, will the approximation ability of NN+Dot-Product-projection be affected? 2. A deeper discussion on the motivation of this entropy regularization design for linear programming and its related works would be appreciated. For example, is it the first time to formulate such a dot-product projection problem with entropy regularization in literature? 3. Providing more detailed information about the problem sizes used in experiments (e.g., dimensions of m and n) would help in assessing the scalability and practical applicability of GLinSAT. 4. Since GLinSAT is designed for continuous problems, the experiments contain 3 discrete problems. It would be beneficial for the authors to explain in detail how GLinSAT is applied to these discrete problems and how feasibility over discrete decision variables is recovered. 5. Why not compare GLinSAT with CvxpyLayers/OptNet with the L2 projection? 6. Why can the feasibility of GLinSAT not be guaranteed in Table 6?

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

The authors have discussed limitations in Appendix A3.

Summary

This paper proposes a new architecture named GLinSAT that projects the output of a neural network to the feasible region of bounded and general linear constraints. The approach is based on a gradient-based approach for solving an entropy-regularized linear program and can be implemented with backpropagation/differentiation. Numerical results are reported for several tasks.

Strengths

1. Outputing solutions satisfying linear constraints is an important topic and the idea in this paper is reasonable and smooth. 2. The method works for general linear constraints and can be implemented efficiently (free of matrix factorization and can be differentiated with backpropagation). 3. The numerical results look nice compared with previous works.

Weaknesses

The authors do not discuss how integer constraints are satisfied when some entries of $x$ are constrained to be integers. Note that several tasks in the numerical part are optimization over integer variables.

Questions

How do you choose $\theta$ in practice?

Rating

5

Confidence

2

Soundness

3

Presentation

3

Contribution

3

Limitations

The authors clearly discuss limitations in Appendix A.3.

Summary

The main contribution of this paper is a method for enforcing arbitrary linear constraints on the outputs of a neural network. This is achieved in a differentiable way so that the entire pipeline can be trained end to end to solve constrained optimization problems. This is achieved by viewing the problem of projecting the outputs of the neural network to the feasible region as an entropy-regularized LP. This in turn can be reformulated as a convex unconstrained optimization problem with Lipschitz gradients. The problem is solved via adaptive primal-dual gradient descent and the authors provide a more efficient way to perform the backward pass than by just calling autodiff. The method is significantly more efficient than previous work and it works well on several problems.

Strengths

- I think this is an interesting approach to satisfying linear constraints on the outputs of a neural network and it builds nicely on ideas from the OT literature. - The proposed method is considerably more efficient than previous works and it improves nicely over previous work on positive linear satisfiability via OT. - Empirically, the proposed method seems to improve over previous work.

Weaknesses

- In terms of contribution, I would argue that this is somewhat incremental, given that previous works can handle some of the same problems. The method here is not limited by positivity like Linsatnet,which is nice, but I am not convinced it's a sufficiently strong contribution. However, there is another stated benefit of the method which is its computational efficiency. This leads me to my next point. - My main concern regarding the experimental evaluation is the scale of those experiments. For example, the TSP results are on quite small instances (20 nodes) which is quite far from anything that could be considered practical. How far can the method scale and how well does it do compared to a solver in those cases? The introduction of the paper argues that solvers can be quite expensive in order to motivate a neural approach but how does Gurobi do on those same problems. How much time does it take to solve them? Is there any setting in which this approach is competitive with Gurobi? I am asking this because for some combinatorial optimization problems (including classical TSP) there are neural network-based approaches that can have competitive results vs Gurobi given a certain time budget. How does the method here do against Gurobi for different budgets? Overall, I like the direction of the paper and the approach it takes but I am not convinced by the empirical results. I start with a tentative score which I will update after the rebuttal.

Questions

see above

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

2

Limitations

n/a

Thanks for your rebuttal

The rebuttal provided has addressed my concerns and questions. I will adjust my evaluation scores accordingly.