Apollo-MILP: An Alternating Prediction-Correction Neural Solving Framework for Mixed-Integer Linear Programming

I have a few concerns below.

• Generally, this paper presents some theorems under several very strong assumptions. I do not think this paper has theoretical contribution, it is more about presenting an empirical algorithm. For example, in Theorem 4, "If the trust-region searching problem 2 is feasible....", the theorem is clearly valid if this assumption is true. I do not think this is worth a theorem.

• Assumption 1 is kind of too strong and counter-intuitive, can you provide some experiments for validation?

• To compare the proposed method against ND [1] and ConsPS [2], I believe it is essential to reproduce some of the experiments presented in their original papers to ensure that ND and ConsPS are indeed comparable.

• In Table 6, we notice that the parameters $k_0$, $k_1$, and $\Delta$ differ significantly from those used in PS's paper [3]. Why did you choose not to use the original parameters? Parameters can directly influence the performance of both the PS and the fixing strategy. For a fair comparison, we recommend the authors employ the optimal parameters for your baseline methods.

• To clearly demonstrate the performance of Apollo-MILP, I suggest including at least two experiments in your ablation study.

  • Case i: Apollo-MILP v.s. 4 rounds of Direct Fixing;
  • Case ii: Apollo-MILP v.s. 4 rounds of PS;

  All these methods utilize the same parameters $k_0^{(i)}, k_1^{(i)}$ and $\Delta^{(i)}$, except in the case of Direct Fixing, where $\Delta$ is not present. In each iteration, the solving times are consistent across these methods. By conducting these two experiments, you can effectively demonstrate that the performance improvements result from Apollo-MILP's multi-stage correction rather than from direct multi-stage solving (e.g., 4 rounds of PS and 4 rounds of Direct Fixing). Additionally, this approach will highlight the effectiveness of combining prediction and correction within your framework.

Minor Issues:

• typo: page 6, paragraph 2. “Instead, UEBO offers a practical estimation by utilizing the available distributions $p_θ(x_i | I)$, $q(x | \hat x_i, I)$”, $q(x | \hat x_i, I)$ is missing an $i$.

• The WA's figure is missing in Fig.3

[1] Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid Von Glehn, Pawel Lichocki, Ivan Lobov, Bren- dan O’Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, et al. Solving mixed integer programs using neural networks. arXiv preprint arXiv:2012.13349, 2020.

[2] Taoan Huang, Aaron M Ferber, Arman Zharmagambetov, Yuandong Tian, and Bistra Dilkina. Con- trastive predict-and-search for mixed integer linear programs. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp (eds.), Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pp. 19757–19771. PMLR, 21–27 Jul 2024. URL https://proceedings.mlr.press/v235/huang24f.html.

[3] Qingyu Han, Linxin Yang, Qian Chen, Xiang Zhou, Dong Zhang, Akang Wang, Ruoyu Sun, and Xi- aodong Luo. A gnn-guided predict-and-search framework for mixed-integer linear programming. In The Eleventh International Conference on Learning Representations, 2023

1. Time-Consuming Data Collection: For my understanding, a key limitation is the time-consuming nature of data collection. Since the model requires optimal or near-optimal solutions as labels during training, it depends on solving many problem instances, which can be computationally expensive for large problems.
2. Limited Benchmark Problems: The number of benchmarks is 4, which, while indicative, may limit the generalizability of the results. Although it is understandable that solving large-scale MILPs can be time-consuming, expanding the experimental scope to include more problems, even some smaller-scale instances, would provide a more comprehensive view.

1. The presentation of the paper can be improved with better introduction of the background and basic concepts. For instance, Proposition 1 uses the concepts of entropy and KL divergence, which should be defined in the context of solution prediction for MILPs.

2. The general framework would be clearer if Algorithm 1 from Appendix B were incorporated into the main text alongside the description in Section 4. Moving the algorithm into the main content could improve readability and help readers follow the approach more easily.

W1. Table 8 says that the CA instances have 1500 variables and ~2500 constraints. The “Hard” instances of CA from Gasse et al. Have 1500 bids, which I believe corresponds to 1500 decision variables. However, their Table 2 “Hard” column for CA shows that SCIP with RPB branching (the default in SCIP) has an average running time of 136.17 seconds, meaning all or most instances are solved to global optimality in 2.5 minutes on average. In contrast, your Table 1 for CA shows that Gurobi typically terminates with a suboptimal solution in 1000 seconds. This is extremely puzzling to me as Gurobi is faster than SCIP and you are likely using better CPUs than used in Gasse et al. Could you clarify whether your CA instances in Table 1 correspond indeed to the “Hard CA” instances of Gasse et al.? Could you explain the performance discrepancy? These instances seem to be super easy to solve to optimality; why does this not apply in your experiments?

W2. Please clarify how you calculate the UEBO, particularly the second term. I have struggled to interpret the conditional version of the q(.) distribution that seems so crucial to this bound. Perhaps a small numerical example is in order for this rebuttal and updated versions of this paper.

W3. Solvers such as Gurobi can be used to emphasize finding good solutions quickly. In particular, MIPFocus=1 (https://www.gurobi.com/documentation/current/refman/mipfocus.html). Do you use this for the “Gurobi” row of your results Table 1? If not, then you should as it is unfair to compare to default Gurobi on primal gap when it is running to balance between proving optimality and finding solutions. It should focus on the latter.

W4. Warm-starting Gurobi as baseline: What if you passed the initial GNN prediction (fixing the k0 and k1 variables to 0 and 1 and letter other variables free) to Gurobi as a MIPStart (https://support.gurobi.com/hc/en-us/articles/360043834831-How-do-I-use-MIP-starts)? Gurobi can search around this warm-start and various ways and it has parameters that let you control this process. I believe this baseline is crucial to understanding the benefits of your and other similar methods. The methods you compare to may have missed this, but that does not justify you not performing this experiment.