Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper considers a neural network based algorithm for solving MILPs. The main novelty lies in the proposed trust region algorithm to construct solutions from the output of the neural network.

strength_and_weaknesses: I think the paper considers an interesting problem, which is potentially of value to those working in the field of machine learning for combinatorial optimization. My specific comments and questions are as follows:

1) I think a more detailed comparison with the neural diving method of Nair et al 2020 would be really interesting. The authors mention the work of Nair et al 2020, however, it is not clear how the performance of their approach would compare.

2) In addition, I think it is interesting to consider how the performance of other neural network based MILP solver methods would compare against the proposed method.

3) The algorithm to solve Eq 11 seems critical for the proposed framework. In my opinion, it would increase the readability to include this algorithm in the main body of the paper.

4) Is the algorithm/solver for SOLVE(M’) in Alg. 1 discussed somewhere in the paper?

5) I think a simple yet interesting baseline to compare with the proposed method is by simply solving the relaxed LP and running the trust region algorithm on the solution of the relaxed LP.

6) As far as I understand, the reported numerical results are for the MILP instances in the test set, not training or validation set. Is this correct? Also, is this explicitly stated somewhere?

7) I think it would be nice to include a discussion on the neural network generalization. How does the performance on the training set compare to performance on the test set?

8) In my opinion, the claim that “Most of the end-to-end approaches directly predict solutions to MILP problems, ignoring feasibility requirements enforced by model constraints. As a result, the solutions provided by ML methods could potentially violate constraints.” needs references to some works where this is the case. 

Minor issues:
1) The font size for Fig.3 is too small.
2) Typo in second sentence of the conclusion: supervise(d)-learning
3) Typo in page 8: “are took into consideration”
4) Typo in page 7, equation (6) and (6)
5) Extra parenthesis in the second line of the equation block for L(\theta): logp_(
6) Typo in the line under eq 11, \hat{x}_I - \hat{x}_I

clarity,_quality,_novelty_and_reproducibility: The clarity could be improved in my opinion by focusing more of the presentation on what is new to this work such as the trust region algorithm.

summary_of_the_review: I think the paper is interesting, however comparison to other work seems could be improved.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The authors propose a predict-and-search framework for solving mixed-integer linear programming (MILP) problems. Specifically, they first predict the solution distributions, and then search for near-optimal solutions within a trust region constructed from the prediction. Experiments demonstrate that the proposed framework improves the performances of two state-of-the-art optimization solvers SCIP and Gurobi on several datasets.
strength_and_weaknesses: Strengths:
1. The proposed predict-and-search framework is novel.
2. The trust region in the search algorithm is well designed.
3. Experiments demonstrate that the proposed framework improves the performance of SCIP and Gurobi on several datasets.

Weaknesses:
1. The paper is hard to follow as the presentation of the proposed approach is unclear. For example, the definition of the so-called “weighted conditional marginal probability distribution” is confusing.
2. The authors may want to add more baselines to demonstrate the effectiveness of the proposed approach. For example, as the predicting part of the method mainly follows [1], the authors should add [1] as a baseline.
3. The authors may want to further discuss on the connections and differences between the proposed predict-and-search approach and existing predicting based (e.g., [1]) and searching based methods (e.g., [2]).
4. The authors only consider discrete variables to be binary, which limits the applications of the proposed framework.
5. In the 4th line in Section 5.2, why are the values of the size parameters the same?

Minor Issue:
1. The authors may want to use “\citep{}” instead of “\cite{}” for some of the citations.

[1] Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid von Glehn, Pawel Lichocki, Ivan Lobov, Brendan O’Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, Ravichandra Addanki, Tharindi Hapuarachchi, Thomas Keck, James Keeling, Pushmeet Kohli, Ira Ktena, Yujia Li, Oriol Vinyals, and Yori Zwols. Solving mixed integer programs using neural networks, 2020.

[2] Li Z, Chen Q, Koltun V. Combinatorial optimization with graph convolutional networks and guided tree search[J]. Advances in neural information processing systems, 2018, 31.
clarity,_quality,_novelty_and_reproducibility: 1. The presentation is unclear.
2. The predict-and-search framework is novel.
3. The authors did not provide any materials to ensure the reproducibility.
summary_of_the_review: Overall, I believe that this paper is marginally below the acceptance threshold. Though the authors propose a novel predict-and-search framework for solving mixed-integer linear programming problem, they miss some important baselines to demonstrate the effectiveness of their proposed framework. Moreover, they may want to improve the writing.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper presents a heuristic for constructing good feasible solutions for families of related mixed-integer linear programming (MILP) problems. The heuristic proceeds by taking an instance from a given MILP family and 1) using a machine learning model to output weights (roughly: approximate solution values) for each decision variable, then 2) solve a sub-MILP in the (small) neighborhood around the point proposed by the predictive model. Computational results suggest that this heuristic can outperform the suite of heuristics in SCIP and Gurobi.
strength_and_weaknesses: The proposed method is a natural and reasonable upon ML-based heuristics that are based on variable fixing. While this extension is not particularly deep and uses "off-the-shelf" concepts, the computational results seem to indicate its utility. The paper is extremely well-written and does a great job introducing each of the concepts used to develop the algorithm.

Why did the authors not compare against the ML-based fixing algorithms that they reference in the introduction? That seems to be the fairest baseline for comparison, as these algorithms are the most similar in setting and approach to the one presented by the authors.

I would appreciate more detail (in the appendix, but also some in the text) about the implementation details of the algorithm. For example, I am curious how the algorithm is implemented with SCIP and Gurobi -- presumably it is used via a heuristic callback with both solvers? If so, can the authors break out how much time is spent in the callback (and how many calls), and what fraction of the total allotted wall time this eats up?


clarity,_quality,_novelty_and_reproducibility: What is the "pre-processing" time required by the new algorithm: e.g., model training, but also the time required to select hyperparameters like Delta, k_0, and k_1?
summary_of_the_review: The paper is very well-written, and provides a natural but worthwhile extension of a recent stream of algorithms for producing heuristic solutions to families of related MILP instances. My concerns are mostly based around the baseline for comparison used in the computational section.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: Authors propose a primal heuristic for solving MIP, following much of Neural Diving strategy from Nair et al (2021). Instead of fixing predicted variables from ML model, authors propose to solve a modified MIP problem which constrains the solution space to be the L1 ball around the predicted solution. Authors demonstrate across two datasets from ML4CO competition and two synthetic datasets from Ecole package that the proposed method works better than the baseline of fixing variables from predicted solution.
strength_and_weaknesses: The main strengths are the simplicity of the approach and the practical appeal. It is conceivable predicted variables from ML model is often not feasible, hence making only a "soft" commitment and searching in an L1 ball seems like a practically useful solution. The method is also conceptually simple and intuitive.

The main weakness of this paper is that the paper builds upon Neural Diving of Nair et al (2021) but authors don't compare against Neural Diving. While Neural Diving uses SelectiveNet to identify variables to fix, authors simply rely on confidence scores. Hence it is unclear whether the proposed predict-and-search (PS) method is superior to fixing strategy, or this is just the consequence of using a naive method for uncertainty quantification. I understand an open-source implementation of Neural Diving is not available (as far as I know), but given high similarity of the proposed method and Neural Diving, I still think authors should've implemented SelectiveNet (the only component that seems to be missing in the current implementation) and compare against full Neural Diving algorithm from Nair et al.
clarity,_quality,_novelty_and_reproducibility: Clarity: The basic idea of the paper is easily understandable. Authors do a reasonable job describing the intuition behind their work. However, authors make a few mistakes in mathematical notations and description of experiments, which poses a moderate difficulty clearly understanding the paper.

Quality/Novelty: The proposed method is a relatively simple refinement of Neural Diving. However, the strategy of using L1-constrained optimization instead of fixing variables seems like a practically useful & broadly applicable idea. Hence this strategy might indeed make a good impact if its empirical advantage against Neural Diving is well-established. As mentioned in Strengths & Weaknesses, however, authors don't compare against full-fledged Neural Diving with SelectiveNet, and thus it is a bit difficult to evaluate whether the proposed method actually has an empirical advantage.

Reproducibility: I don't see source code, generated datasets, or scripts being shared in supplementary material. Hence reproducing this paper will take a considerable effort re-implementing the training code as well as integration with SCIP/Gurobi. 

A few detailed notes on clarity:

Section 3.1.2. Equation (7). It's worth mentioning this factorization is also proposed from Nair et al.

In equation (8), shouldn't this be normalized by $|L_i|$ to be a value between 0 and 1?

Under equation 11, $||\hat{x}(I) - \hat{x}(I)||$ seems to be a typo of $||\hat{x}(I) - x(I)||$.

As authors themselves mention, proposition 1 is quite obvious. Usually such obvious fact should just be mentioned in the narrative rather than dedicating a proposition.

gap_p in Table 1 doesn't seem to be explained. It seems like the percentage of the improvement of the gap.

In Section 5.1, I wonder how $(k_0, k_1)$ and $\Delta$ were chosen in these experiments? 

In Section 5.2, $(k_0, k_1)$ values are repeated as (700, 0) four times. Seems like a mistake?
summary_of_the_review: While the paper heavily builds upon Neural Diving of Nair et al (2021), authors deviate from Neural Diving in their decision to not use SelectiveNet for uncertainty quantification. Hence, it is unclear whether the claimed improvement over the fixing strategy is the consequence of using a naive uncertainty quantification method, or the benefit of the proposed Predict-and-Search strategy.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: All reviewers find the paper's proposal appealing (from the most negative review: "It is conceivable predicted variables from ML model is often not feasible, hence making only a "soft" commitment and searching in an L1 ball seems like a practically useful solution. "), and all are satisfied that the novelty over Neural Diving (ND) of Nair et al is sufficient.

The original paper had not compared against ND, but post-rebuttal, these comparisons are included, and show the advantages of the paper's proposal over the existing work.

Reviewers did not update their scores post rebuttal, but the paper has been carefully considered by the AC and SAC, and discussed with the PC chairs, and it is clear that the post-rebuttal paper is significantly stronger than the original paper, to which the numerical scores applied.  Hence, the text of the reviews, combined with the post-rebuttal improvements to the paper, supercedes the raw numerical scores in accepting this paper.

For final copy, the comparison with ND should be moved from the appendix to appear prominently in the main paper---all reviewers (and the authors) agree that ND is closely related work.  The authors reasoning that ND "has not yet been accepted by any academic journals or conference proceedings" is understandable, in the view of the AC and SAC, given the paper's 100 citations, it is /de facto/ an academic publication.

justification_for_why_not_higher_score: Novelty is sufficient over ND, but not to spotlight level.
justification_for_why_not_lower_score: The post-rebuttal comparisons prove the contribution of the paper.
Decision: Accept: poster