Learning to Optimize for Mixed-Integer Nonlinear Programming

Authors: Bo Tang, Elias Boutros Khalil, Jan Drgona
Primary area: optimization
Keywords: Mixed-Integer Nonlinear Programming, Learning to Optimize, Differentiable Optimization, Constrained Neural Networks, Deep Learning, Operations Research

Abstract:
Mixed-integer nonlinear programs (MINLPs) arise in various domains, such as energy systems and transportation, but are notoriously difficult to solve. Recent advances in machine learning have achieved remarkable success in optimization tasks, an area known as learning to optimize. This approach includes using predictive models to generate solutions for optimization problems with continuous decision variables, thereby avoiding the need for computationally expensive optimization algorithms. However, applying learning to MINLPs remains challenging primarily due to integer decision variables, which complicate gradient-based learning. To address this limitation, we propose two differentiable correction layers that generate integer outputs while preserving gradient information. The experiments demonstrate that the proposed learning-based approach consistently produces high-quality solutions for parametric MINLPs extremely quickly. As problem size increases, traditional exact solvers and heuristic methods struggle to find feasible solutions, whereas our approach continues to deliver reliable results. Our work extends the scope of learning-to-optimize to MINLP, paving the way for integrating integer constraints into deep learning models.

Decision: reject
Reviewer scores: 6, 5, 3, 3

Reviews and discussion:
<thread>
creation date:
1730020760732

thread_type:
official_review

<thread_object>
creator: reviewer_refb

<content>
summary:
This paper proposes an end-to-end optimization method for solving general mixed-integer nonlinear programs (MINLPs). The proposed approach consists of two steps to generate solutions. In the first step, a neural network is employed to generate a relaxed solution that is close to the optimal solution. In the second step, another neural network provides update directions for continuous variables and rounding rules for integer variables. All of these neural networks are trained in a self-supervised manner. The Straight-Through Estimator is utilized to manage non-differentiable operations, such as rounding.

strengths:
This paper focuses on applying machine learning methods to solve MINLPs. 
- It proposes novel differentiable correction layers that can potentially handle the non-differentiability of integer outputs in deep learning models.

weaknesses:
I have a few serious concerns below.

- First and foremost, since the proposed approach does not take advantage of the non-linear part, I think it could also be applicable to mixed-integer linear programs. Then why not also conduct computational experiments on those instances and show how good or bad it performs? We know that learning to solve MINLPs is rarely studied but being the first to address such a problem could be a trivial thing (not a significant contribution). 

- Note that in the computational studies, only the right hand sides of constraints are perturbed, I recommend the authors perturb all parameters in the MINLP formulations and conduct experiments. The reason I ask such a question is, representing MINLPs using neural networks itself is a very important question (and challenging). Note that representing linear programs or mixed-integer linear programs via neural networks has theoretical foundations, see [1] [2]. Furthermore, I do not see equality constraints in the dataset. 

- Can the authors consider more practical MINLP instances? Such as MINLPLIB (https://www.minlplib.org/). The dataset used in the manuscript is kind of like toy problems. I'm expecting to see the computational performances on real-life instances.

- The parameter $\lambda$ in loss function is an import hyper-parameter for balancing feasibility and optimality, and should be analyzed more carefully. Usually, penalty methods in L2O demonstrate very weak generalization capabilities. This kind of explains why the infeasibility ratio in Table 4 is so high. I do not think penalizing constraints in the loss function is a good way. Rather, the authors should design special algorithms to handle nonlinear (and possibly non-convex) constraints. 

[1] Chen, Z., Liu, J., Wang, X., Lu, J. and Yin, W., 2022. On representing linear programs by graph neural networks. arXiv preprint arXiv:2209.12288.

[2] Chen, Z., Chen, X., Liu, J., Wang, X. and Yin, W., 2024. Expressive Power of Graph Neural Networks for (Mixed-Integer) Quadratic Programs. arXiv preprint arXiv:2406.05938.

questions:
See the weakness part.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730467431347

thread_type:
official_review

<thread_object>
creator: reviewer_bmkz

<content>
summary:
This paper addresses the challenging problem of Mixed-Integer Nonlinear Programming (MINLP) within a learning-to-optimize framework, a crucial area of research with significant applications across various domains. The integration of learning approaches into MINLPs is particularly complex due to the presence of integer decision variables, which complicates gradient-based optimization techniques. To tackle this issue, the authors propose two differentiable correction methods that enable neural networks to generate high-quality integer solutions while maintaining gradient information for backpropagation. Additionally, the authors conduct a comprehensive set of experiments to demonstrate the superiority of their proposed methods compared to traditional exact search algorithms and heuristic approaches.

strengths:
1. MINLPs arise in numerous real-world applications, making the techniques proposed in this paper significantly relevant to practical problem-solving.

2. The paper is well-structured and clearly articulated, making it accessible to the reader.

3. The authors assert that they are the first to introduce Straight-Through Estimator (STE) and Gumbel-Sigmoid techniques in the context of learning-to-optimize, which they identify as pivotal for efficiently generating solutions to large-scale MINLP problems.

weaknesses:
1. The fairness of the comparisons and the definitions used in the experiments are unconvincing for several reasons:

   - In lines 324 to 327, the authors list the solvers compared and the corresponding types of problems. However, they do not provide sufficient justification for the selection of these solvers or explain their relevance to the specific problem types addressed.

   - In lines 330 to 334, the authors mention modifications made to the original quadratic problems from Donti et al. (2021), but it remains unclear whether these modifications confer any advantages to the proposed method. Clarification is needed.

   - The metrics employed in the experiments raise concerns. For instance, while generating low percentages of infeasible solutions quickly is noted, the implications of this metric are questionable. The time required to convert an infeasible solution into a feasible one can be substantial, thus diminishing the significance of the reported speed.

   - In the experiments involving simple nonconvex problems, the use of the %Unsolved metric is unconventional. It is problematic to claim a problem is solved when the provided solution is still infeasible.

2. The loss function introduced in the paper essentially applies the Lagrangian multiplier method, which is not particularly novel in this field.

3. Additionally, there are several typographical errors throughout the paper. The authors should conduct a thorough proofreading before submission.

questions:
1. In lines 330 to 334, the authors mention modifications made to the original quadratic problems from Donti et al. (2021). However, it remains unclear whether these modifications provide any advantages to the proposed method. A clarification on this point is necessary.

2. In Algorithm 1, the authors only consider a round-down direction for integer variables. It would be beneficial to explain why the round-up direction is excluded. If the round-up direction is relevant, this should be described in detail.

3. In the experiments, the authors allocate only a 60-second time budget to the exact solver. This limited timeframe may hinder the solver’s ability to find the optimal feasible solution, even if a few additional seconds are provided. It would be more informative to present a statistical distribution of % Infeasible versus Time (seconds) for the various methods evaluated.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730470545285

thread_type:
official_review

<thread_object>
creator: reviewer_gthk

<content>
summary:
This paper proposes two differential correction layers (rounding classification and learnable threshold) that generate integer outputs while preserving gradient information.  The experiments demonstrate that the proposed learning-based approach consistently produces high-quality solutions.

strengths:
- The topic of MINLP is an interesting and important topic in the field of learning to optimize.
- This paper combines the gradient information during the optimization.
- The presentation in this paper is good.

weaknesses:
- The STE is not novel in the ML field. Moreover, the author may want to explain that combining the gradient information cannot lead to local optima.
- While many works on learning to optimize use GNN to process problems with different sizes, the proposed method seems to use MLP with fixed-size inputs. Thus, the network may fail to process problems of various sizes.
- The author may investigate the effects of different $\lambda$ on the performance.
- The author may conduct experiments on more complex instances, and the 60-second time limit is too short. Existing works in learning to optimize conduct experiments on challenging instances with at least 1000 sec of time limit [1,2].

[1]  A GNN-Guided Predict-and-Search Framework for Mixed-Integer Linear Programming

[2] GNN&GBDT-Guided Fast Optimizing Framework for Large-scale Integer Programming

questions:
- Could you please explain how the proposed method handles problems with different sizes?
- Could the proposed method generalize to large instances, such as those with thousands of constraints and variables?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730680873888

thread_type:
official_review

<thread_object>
creator: reviewer_rkoe

<content>
summary:
The paper proposes an end-to-end method for learning solutions of integers programs by enabling differentiation through the rounding operation within model training. This is done by using the Straight-through Estimator (STE) combined with the Gumbel-noise method, which smooths the discrete function representing the rounding operations to obtain useful gradients for backpropagation. The paper provides a comprehensive evaluations of the proposed method across several optimization tasks.

strengths:
The paper is well written and organized. The idea of integrating the rounding operations within model training is sound and allows to obtain superior models with respect to Learning to Optimize models who solve a relaxed version and perform the rounding operations at inference time, as shown in the experimental sections. Computational advantages are also significant with respect to traditional numerical solver.

weaknesses:
My main concern is that the proposed method cannot ensure constraint satisfactions, since it uses a soft constraint approach. I believe that integer variables also makes difficult to perform projections to restore feasibility at inference time. Nonetheless, the percentage of infeasible solution generated by the proposed method is low, and the results shown in the Table 5 suggest that using a Lagrangian-inspired method might allow to obtain a better estimate of the dual variables, which might help to reduce constraint violations. 
The paper might benefit from a more systematic evaluation of the impact of different constraint functions to the feasibility/violations produced by the proposed method, which might allow to identify scenarios and pattern where the proposed method (does not) produce constraint violation.

questions:
Could you please expand on the constrain violations produced by your method? Do you have an understanding of how the proposed method handle different constraint functions? For instance, what type of constraint are well-handled? What, instead, are more difficult to satisfy?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732150421423

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
A Comment to the Reviewers to Clarify the Contribution and Announce the Updates

comment:
We appreciate the reviewer’s time and effort in providing detailed feedback. We would like to take this opportunity to clarify the contributions and highlight the updates made to strengthen the paper based on the reviewer’s suggestions.
 
**Contribution:**

1. **Efficient Learning-to-Optimize (L2O) method for parametric mixed-integer nonlinear programming (MINLP).** We propose a novel two-network architecture tailored for the challenging domain of general parametric MINLPs. This simple yet efficient end-to-end framework can be trained within a few hundred seconds offline and provide extremely fast inference in milliseconds using standard hardware. We demonstrate that the proposed method produces high-quality solutions with a strong feasibility rate for large-scale instances, even for problems where traditional solvers (including SOTA commercial solvers) struggle to find any feasible solution in a reasonable time.

2. **Self-Supervised Learning without the need for labeled data generated by classical solvers.** The proposed architecture can be effectively trained with first-order gradient solvers in a self-supervised setting using the Lagrangian loss function without requiring optimal solutions as labels. This self-supervised approach avoids the computational overhead of collecting large-scale labeled data from classical numerical solvers such as Gurobi or SCIP. This makes our framework particularly practical and scalable for solving high-dimensional parametric MINLPs as we demonstrate in our extensive experimental case study section.

**Updates made to the manuscript:**

1. **1000-second time limit (Section 6.2):** We conducted additional experiments with a 1000-second time limit for convex quadratic problems. These results demonstrate that our methods still outperform baselines by a substantial margin. For the simple non-convex problem (Section 6.3) and the Rosenbrock problem (Section 6.4), experiments with a 1000-second time limit are currently underway. Once complete, these results will also be included in the manuscript.

2. **Larger instances (Section 6.2 and 6.3):** We performed experiments on larger problem instances, including 1000×1000 convex quadratic problems and 1000×1000 non-convex problems, i.e., problems with 1000 decision variables and 1000 constraints. These scales illustrate the robustness and scalability of our approach. It is important to note that these problem sizes are significantly larger than most benchmark problems (e.g., 100×100) used in the current learning-to-optimize literature for continuous cases [1,2].

3. **Penalty weight analysis (Section 6.5):** We conducted a detailed analysis of the effect of penalty weights on solution quality and constraint satisfaction. As expected, increasing the penalty weights improves feasibility rates but may slightly degrade objective values. This trade-off underscores the importance of tuning penalty weights carefully. 

4. **Sample size analysis (Section 6.6):** We examined the impact of varying training sample sizes on model performance for 20000×4 Rosenbrock. Larger training datasets significantly reduced infeasibility rates and improved generalization to unseen instances. Notably, since our method is self-supervised and does not require optimal solutions as labels, the cost of increasing the training sample size is remarkably low, making this approach both practical and efficient for large-scale problems.

5.  **Ablation studies (Appendix F):** We added ablation studies to isolate and evaluate different aspects of our method, such as the impact of the end-to-end learning and the differentiable integer correction, to better understand their contribution to overall performance.

6. **Constraint violation analysis (Appendix G):** We analyzed constraint violations in terms of both frequency and magnitude across three benchmark problems. This provides a detailed understanding of how well our method satisfies constraints.

7. **MILP experiments (Appendix H):** We have conducted additional experiments for MILP from the MIP Workshop 2023 Computational Competition to evaluate the generalizability of our methods.

[1] DC3: A learning method for optimization with hard constraints

[2] Self-Supervised Primal-Dual Learning for Constrained Optimization
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper proposes a gradient-based learning method to generate integer solutions for mixed-integer nonlinear programs (MINLPs). To address the challenge of handling non-differentiable operations in predicting integer variables, the paper introduces two differentiable correction layers—rounding classification and learnable thresholds—that provide useful gradients for backpropagation. Experiments demonstrate the method’s effectiveness in producing high-quality solutions.

However, the reviewers have pointed out some important weaknesses. First, the proposed method primarily combines existing differentiable techniques, which limits the contribution of the paper. Second, more insights are needed on improving constraint satisfaction, especially for large-scale instances with nonlinear constraints. Third, the paper should evaluate more practical instances with large scales or diverse constraints to provide a more comprehensive understanding of the method's performance. Therefore, I recommend the next version of this paper to incorporate more insights and experiments.