Learning to Optimize for Mixed-Integer Nonlinear Programming

Thank you for the detailed comments which we address next in this response as well as in the updated version of the submission.

1. Experiments for MILP:

   • We agree and have already performed experiments on MILP problems. In Appendix H, we conducted additional experiments on MILPs using the Obj Series 1 dataset from the MIP Workshop 2023 Computational Competition (https://github.com/ambros-gleixner/MIPcc23). The results demonstrate that our learning-based methods generate high-quality, feasible solutions efficiently, even outperforming the heuristic solution obtained at the root node in terms of objective value. For this dataset, finding the optimal solution for these instances requires approximately 30 seconds, whereas the root node heuristics has an efficiency advantage (0.01 sec) over our methods (0.04 sec).

2. Lack of significant contribution:

   • We respectfully disagree. The field of MINLP is large and growing, as evidenced by the focus attributed to MINLP in the solvers SCIP and Gurobi, both of which have been progressively expanding their capabilities to tackle non-convex MINLPs. This is likely due to practical applications requiring this capability. As you have noted, representing MINLPs is challenging. Our work takes a first step towards expanding the learning-to-optimize literature to MINLP by considering parametric versions of the problem. This allows us to focus on producing integer solutions, something that has not been tackled in prior work, even on MILP, and on constraint satisfaction. This is enabled not just by the loss function, but also the two-network architecture and the differentiable correction layers that are empirically very effective at generating feasible assignments to integer variables. For example, we have demonstrated the practical value of our approach through experiments on large-scale instances, such as the 200×200 convex quadratic problem and even larger instances, where traditional solvers and heuristic methods fail to find any feasible solution within reasonable time limits. In contrast, our method achieves feasible solutions with short training times and rapid inference speeds, often yielding high-quality results. If the reviewer is aware of other work that tackles these issues directly, we would appreciate some references.

3. Only perturbed the RHS:

   • Thank you for those references, which we have commented on in the Related Work section of the updated paper.
   • The mixed-integer Rosenbrock problem is parameterized by an n-dimensional vector $a$ in the objective as well as the scalar $b$ in the constraints.
   • Additionally, in Section 6.2 of the updated paper, we have expanded the experiments to include perturbations to the constraint matrix A through an m-dimensional vector $d$, further broadening the scope of parameterization.

4. Lack of equality constraints:

   • Generating a feasible equality constraint with integer variables can be highly non-trivial as it is at least as hard as the NP-Complete Subset-Sum problem. Generating a system of feasible equality constraints is even harder. In the absence of a reliable equality generation scheme, we opted to stick with inequality constraints, which are also extremely common in practice.

Dear Reviewer,

This is a kind reminder that the dicussion phase will be ending soon on November 26th. Please read the author responses and engage in a constructive discussion with the authors.

Thank you for your time and cooperation.

Best,

Area Chair

Thank you for the detailed comments which we address next in this response as well as in the updated version of the submission.

1. Solver selection (Why Gurobi & SCIP?):

   • Both are generic MINLP solvers with some of the best-reported results according to independent benchmarking (see, for example, https://plato.asu.edu/ftp/minlp.html) as well as academic licenses for research. In fact, as noted by Lundell & Kronqvist (2022) (see [1] below for ref.), who performed a comprehensive benchmarking of more than ten MINLP solvers: “It is clear, however, that the global solvers Antigone, BARON, Couenne and SCIP are the most efficient at finding the correct primal solution when regarding the total time limit. [...] Gurobi also is very efficient when considering that it only supports a little over half of the total number of problems!”. As such, Gurobi and SCIP are very much representative of the state of MINLP solving.

2. Problem selection (Why change Donti et al’s QP):

   • We describe this instance generation process in more detail in Appendix E of the updated paper. Simply put, Donti et al. studied continuous quadratic problems whereas we are interested in their discrete counterparts. The modifications do not advantage our methods at all. Specifically, we added integrality constraints, which inherently make the problems more challenging, and removed equality constraints to avoid infeasible instances in our discrete setting. These changes were necessary to adapt the problems to the discrete domain, but they do not alter the problem in a way that benefits our proposed methods.

3. Feasibility issue:

   • Indeed, the neural network output may not be feasible, though our training loss function encourages the model to produce feasible solutions, and our empirical results show rather low infeasibility rates. We have expanded the analysis of infeasibility and show that with sufficiently large penalty weights in training and large enough training data, integer-feasible solutions can be generated most of the time; we refer to Section 6.5 and Section 6.6 of the updated paper.
   • Guaranteeing a feasible solution for a MINLP is NP-Hard in general. As such, no heuristic algorithm, ML-based or not, can be guaranteed to produce feasible solutions in polynomial time. However, our ML model output can be passed on to an exact MINLP solver, such as Gurobi/SCIP, which can then attempt to construct a fully feasible solution. In Gurobi, this can be done using “variable hints”.
   • We agree that including a more explicit evaluation of post-processing time and its impact on overall efficiency would strengthen the paper. However, our results already demonstrate that our method provides an efficient, practical, and scalable solution, especially for large-scale instances where solvers fail to find any feasible solutions for each instance within a reasonable time.

4. Metrics (%Infeasible and %Unsolved):

   • Due to numerical issues, it is possible for a MINLP algorithm to produce a solution that is thought to be feasible when it actually is not. We perform this check and record the “% Infeasible" rate. As for the “%Unsolved” metric: Given that MINLPs are NP-Hard to solve, no polynomial-time algorithm is guaranteed to generate a feasible solution in a bounded amount of time. Tracking the number of test instances for which no solution is generated by a method is thus important. We believe that these metrics, in conjunction with objective function value mean/median as well as running time, provide a complete picture of method performance.
   • In our updated experiments, with access to improved computational resources, the simple non-convex problem does not currently exhibit partial unsolved cases within the time limit—i.e., either all instances are solved, or none are. However, for the Rosenbrock problem, we still observe and report the “%Unsolved” metric.

5. Loss function novelty:

   • Indeed, penalizing constraint violations in an objective function is a standard technique for continuous constrained optimization. However, this approach has not been used at all to learn to generate solutions for mixed-integer non-linear programs. Our proposed methods are the first to address learning-to-optimize in the context of general parametric MINLPs. This is enabled not just by the loss function but also by integer outputs from the two-network architecture and the differentiable correction layers that are empirically very effective at generating feasible assignments to integer variables.

6. Typos:

   • We have corrected every typo we could find in the updated version of the submission.

[1] Lundell, Andreas, and Jan Kronqvist. "Polyhedral approximation strategies for nonconvex mixed-integer nonlinear programming in SHOT." Journal of Global Optimization 82.4 (2022): 863-896.

Dear Reviewer,

This is a kind reminder that the dicussion phase will be ending soon on November 26th. Please read the author responses and engage in a constructive discussion with the authors.

Thank you for your time and cooperation.

Best,

Area Chair

Thank you for the thoughtful comments, which we will address next in this response as well as in the updated version of the submission.

1. STE is not novel, and gradient cannot lead to local optima:

   • We would appreciate a clarification on what you mean by this comment about the gradient that cannot lead to local optima so we can address it appropriately. Thank you!
   • We note that we use STE in two novel integer correction layers that we introduce in this paper. We don't claim novelty for the STE itself. These layers build upon the differentiability offered by STE and adaptively adjust the rounding direction. In the newly included ablation study (Appendix F), we explicitly evaluate a baseline method that uses STE alone to round values to the nearest integer (Rounding with STE, RS), and its performance is limited compared to our method.

2. MLP can only process fixed-size inputs vs. GNN in prior work:

   • GNN models for mixed-integer linear programs are suitable because a MILP can be represented exactly by a bipartite variable-constraint graph over which the GNN operates. The same does not hold for our MINLPs, as they can have non-linear constraints. In the MILP case, an edge between a variable and a constraint represents that the variable has a non-zero coefficient in that constraint. The same trick cannot be used for MINLP representation, making a direct application of GNN impossible. Future work on this front would be interesting, though it is orthogonal to what we are proposing here.
   • While our method does not directly adapt to varying problem sizes, its self-supervised nature avoids the need for optimal solutions as labels, allowing us to efficiently train models tailored for large-scale problems without relying on generalization across sizes. For instance, it is practical to train separate models for different problem sizes at a low cost. In contrast, many previous GNN-based methods [1, 2] rely on optimal solutions as labels, which is impractical for large-scale problems to get sufficient labels. This makes scalability and generalization to large-scale problems even more critical. We demonstrate this capability by training on 20000×4 Rosenbrock problems (Sections 6.4, 6.6) and additional experiments on 1000×1000 problems (Sections 6.2, 6.3).

3. Effects of different penalty weights on the performance:

   • As newly added in Section 6.5, and consistent with expectations, we observed improved constraint satisfaction at the expense of worse objective values as λ increases. This trade-off highlights the importance of carefully tuning penalty weight.

4. 1000 sec of time limit for solver:

   • We have performed additional experiments using a time limit of 1000 seconds. The results for the convex quadratic problem are presented in Section 6.2 of the updated submission. Our methods still outperform baselines by a substantial margin. For problems larger than 200×200, exact solvers often fail to find a feasible solution within 1000 seconds—or even hours or days—highlighting the challenges of scaling traditional methods. 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, and we will update the manuscript with these results as soon as they are complete.
   • We do note, however, that a short time limit of 60 seconds is also appropriate for real-time solution generation, which is common to many applications. While increasing the solver time limit may improve the quality of exact solutions, our approach offers a critical advantage: the ability to produce solutions in milliseconds. This efficiency makes our method well-suited for applications requiring real-time or near-real-time decision-making, where longer solver runtimes are impractical.

5. Larger Instances:

   • We have included experiments with 1000×1000 instances in Sections 6.2 and 6.3. In the context of MINLP, these problem dimensions are already considered highly challenging. For instance, with hundreds of variables and constraints, exact solvers such as Gurobi and SCIP often require prohibitively long computation times to produce feasible or near-optimal solutions.
   • 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 [3,4].

[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

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

[4] Self-Supervised Primal-Dual Learning for Constrained Optimization

Dear Reviewer,

This is a kind reminder that the dicussion phase will be ending soon on November 26th. Please read the author responses and engage in a constructive discussion with the authors.

Thank you for your time and cooperation.

Best,

Area Chair

Thank you for the thoughtful comments, which we will address next in this response as well as in the updated version of the submission.

1. Infeasibility handling:

   • Indeed, the neural network output may not be feasible, though our training loss function encourages the model to produce feasible solutions, and our empirical results show rather low infeasibility rates. We have expanded the analysis of infeasibility and show that with sufficiently large penalty weights in training and large enough training data, integer-feasible solutions can be generated most of the time; we refer to Section 6.5 and Section 6.6 of the updated paper. Although the feasibility is not guaranteed, our results already demonstrate that our method provides an efficient, practical, and scalable solution, especially for large-scale instances (e.g. , 1000×1000 quadratic problem and the 20000×4 Rosenbrock problem) where solvers fail to find any feasible solutions for each instance within a reasonable time.
   • In addition, guaranteeing a feasible solution for a MINLP is NP-Hard in general. As such, no heuristic algorithm, ML-based or not, can be guaranteed to produce feasible solutions in polynomial time. However, our ML model output can be passed on to an exact MINLP solver, such as Gurobi/SCIP, which can then attempt to construct a fully feasible solution. In Gurobi, this can be done using “variable hints” .

2. Constraints analysis and penalty weights tuning:

   • As newly added in Section 6.5 and consistent with expectations, we observed improved constraint satisfaction at the expense of worse objective values as λ increases. This trade-off highlights the importance of carefully tuning penalty weight.
   • Additionally, we have expanded our analysis of constraint violations, which is now presented as heatmaps across various benchmark problems in updated Appendix G. Violations in the convex quadratic problem and the simple non-convex problem, are rare and generally minor in magnitude, as illustrated in Figures 6 and 7. When violations do occur, they are concentrated on a single (identical) constraint and affect only a small number of instances. This indicates that most constraints in these problem types are well-handled by our method. In contrast, for the Rosenbrock problem at an extreme scale (20000×4), violations are more frequent and substantial, particularly for the nonlinear constraint $\|\| \mathbf{x} \|\|_2^2 \leq n b$, as shown in Figure 10. By the way, this feasibility issue is significantly mitigated with more sampling data (in Section 6.6).
   • Building on this analysis, we agree with the reviewer that dynamically analyzing and tuning the penalty weights for specific constraints based on their scale and difficulty during training could be a promising approach to improving feasibility rates for challenging constraints. We thank the reviewer for this valuable suggestion, which opens up an exciting direction for future research.

Dear Reviewer,

This is a kind reminder that the dicussion phase will be ending soon on November 26th. Please read the author responses and engage in a constructive discussion with the authors.

Thank you for your time and cooperation.

Best,

Area Chair

We thank the reviewer for their insightful suggestion. Regarding constraint satisfaction, we would like to clarify that it remains a well-known open challenge in the L2O setting, even for simpler cases like MILPs. For example, in L2O for MILP [1,2], infeasibility is also a persistent issue, and part of the contribution lies in reducing its occurrence. Additionally, we note that submission 7722, a concurrent work submitted to ICLR, reports feasibility rates of 50.8%, 97.1%, and 99.4% for MILP problems. It is, therefore, very challenging to expect perfect feasibility from a solver-free approach like ours.

To our knowledge, no solver-free approach guarantees feasibility for general constrained discrete problems, and typical strategies involve either refining the solver's search space to reduce infeasibility or using infeasible solutions as starting points for solvers to repair feasibility.

We believe our work makes a meaningful contribution by significantly lowering the infeasibility rate while maintaining solver-free operation and scalable performance. We thank the reviewer again for their feedback, which encourages us to continue refining and presenting our methods.

[1] Solving Mixed Integer Programs Using Neural Networks

[2] Contrastive Predict-and-Search for Mixed Integer Linear Programs

We would like to inform the reviewers and readers that we have updated the manuscript to update experiments for the Simple Non-Convex Problem (Section 6.3) and the Rosenbrock Problem (Section 6.4) with a 1000-second time limit for solvers. All solver experiments are now performed under this 1000-second time limit for consistency.

1. Convex Quadratic Problem:

   • Our method consistently finds solutions within 0.005 seconds with strong feasibility rates across all problem sizes.
   • Solvers, in contrast, fail to find feasible solutions within 1000 seconds for the 200×200, 500×500, and 1000×1000 problem sizes.
   • Starting from a 10×10 problem size, our method significantly outperforms heuristics on root node

2. Simple Non-Convex Problem:

   • Our method achieves solutions within 0.005 seconds with strong feasibility rates across all problem sizes.
   • Solvers exhibit 86% failure rates in finding feasible solutions within 1000 seconds for the 100×100 problem size and fail entirely for the 200×200, 500×500, and 1000×1000 problem sizes.
   • Starting from a 10×10 problem size, our method significantly outperforms heuristics on root node.

3. Multi-Dim Rosenbrock Problem:

   • For all instances except the largest (20000×4), our method finds feasible solutions in 0.003 seconds or less.
   • For a 2000×4 problem size, 4% of instances can not be solved in 1000 seconds, while for a problem size of 20000×4, this percentage rises to %22.
   • When the solver finds feasible solutions within 1000 seconds, it performs poorly, even for small instances. For example, at the 20×4 problem size, solutions from solvers are significantly worse than those generated by our method.
   • For the largest instance (20000×4), increasing the number of samples during training and adjusting penalty weights can greatly improve the feasibility of our method.

These results further emphasize the efficiency, scalability, and practicality of our approach, especially in scenarios where solvers struggle to find feasible solutions or deliver competitive performance within reasonable time limits. We deeply appreciate your ongoing engagement with our work, and we hope these updates further clarify the contributions and practical significance of our method.