Sampling-Enhanced Large Neighborhood Search for Solving Integer Linear Programs

• I think $\eta$, $\tau$ and $\sigma$ are important parameters in this approach, and the author may want to conduct experiments on the effects of the different parameters.
• The presentation can be improved. The author could explain the advantages of the locally informed proposal and how it can help escape the local optima.
• Lack of necessary references on neural LNS, such as [1] and [2].

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

[2] Light-MILPopt: Solving Large-scale Mixed Integer Linear Programs with Lightweight Optimizer and Small-scale Training Dataset

1. The authors claim they identity the limitation of neural models in escaping local optima theoretically. But little evidence supports this claim.
2. The main algorithms are displayed without any captions to explain the details and not much has been say in the main part of the paper regarding the accept and update functions.
3. We all know simulated annealing method is very sensitive to the hyperparameter settings. As you decay by 0.9 every step in your experiments, have you tried other decay functions and parameters to test the robustness of your method?
4. The experiments have been done in a relatively easy way. More realistic MIP datasets should be used like Item placement, mirplib library and even MIPLIB 2017.

My main concern with this paper is that; at a high level, it is not clear what the paper is trying to achieve.

On the one hand, it starts with a broader question (and indeed a very interesting one!) about the local minimum behavior of LNS, which deserves its study.

On the other hand, it ends up tuning one particular LNS approach, a form of sampling augmented local branching, to perform better than its non-sampling versions and a few other baselines. If I understand it right, the original local branching method has already been shown to be better than the earlier approaches, so essentially, this paper shows that sampling improves over the results of local branching relaxation. This is nice, but rather a limited result compared to the paper's primary goal of "studying the local minima behavior of LNS".

Hence, there is a gap between what the paper proposes to study and what it presents/shows. If we treat the paper as a general study of local optima of LNS (which I find quite interesting!), unfortunately this is not what is experimented for. If we treat the paper as improving the best previous LNS, then it can be interpreted as relatively incremental. (plus, I am not sure if the extended training times lead to a fair comparison in the first place; see my comment below).

The theoretical framework is quite nice, and the intuition that the destroy operator finding a good set of variables for reaching a better solution becoming increasingly small seems reasonable/plausible. What's not clear is how this is related to "neural LNS methods"? What makes this intuition specific to Neural methods only? Your proposal is more general than that, isn't it? Why is local optima only a problem for neural methods for local branching? Does local optima not pose an issue for other LNS destruction methods?

This paper would have been more impactful if it showed, within this neat theoretical model, that sampling and simulated annealing help several destroy operators (neural, non-neural etc.) to perform better than their original versions. In its current form, what is presented is sampling improves one particular LNS method. This is not to undermine the improvements provided by this combination. But in that case, we should not generalize this result too much into "studying the local optima behavior of LNS" and instead post it as a better LNS operator than previous work.

Alternatively, does your theoretical model suggest that other LNS destroy operators without neural network training do not exhibit this behavior? This is hard to believe, or at least not shown in the paper.

Other comments:

• The paper switches the terminology in a few places where sometimes Simulated Annealing is attributed to dealing with local minima, and sometimes Sampling is attributed to coping with local minima. Then, Figure 6 presents an ablation study in which top-k appears to be more effective than SA. If I understand correctly, while the k varies, the SA configuration is static. Could this not be a side effect of the particular hyper-parameterization of the SA? Why would SA prefer a fix/static k for different annealing schedules? If sampling K dominates SA, why is SA part of the overall method in the first place?

• The paper reads, "We could easily model Eq 8 using the feasible solutions found by the ILP solver". How does this work? What are the feasible solutions from ILP? Are we not solving the ILPs with an objective function? How do we obtain only satisfying/feasible assignments? Btw, if it's correct to generate feasible solutions by the ILP solver, than that means any other destroy operator can be augmented with some form of sampling strategy, as you did here for local branching, no?

• Have you considered comparing your sampling approach with some form of restart mechanism? Currently, none of the comparators in the experiments deal with the local optima as discussed here (other than some adaptive neighborhood size, if I understood that correctly, but they are not designed for dealing with local optima). So, I wonder if there would be better baselines (other than a list of different LNS) to better distinguish/address the sampling effectiveness. For instance, how stable is the initial feasible solution? Can the initial feasible solutions not be sampled and the process restarted, as a relatively simple baseline?

• Section 3.3 is hard to understand. Why would the training methodology differ for a sampling version? The goal of the training is to identify a good set of variables for the destruction operation, yes? Do you mean that for sampling, not only suitable destroy variables are needed but also a "diverse" set of suitable variables is required? Hence, more training? Also, if the sampling method is allowed for further training compared to other methods used in the comparisons, this is problematic, isn't it? How do we know the differences are not due to extended training here? Do you have results that compare sampling LNS with other LB LNS using the same amount of training budget?

Minor comments (that did not affect my review)

• when better solutions are far away from the current solution. What does that mean? What is far away? Do you mean objective-wise, or (hamming) distance in solution values, or else?
• The use of quotation marks is inconsistent. Please fix throughout
• typo Loca Balancing
• In parts, the paper refers to a concept called the "optimal destroy variable." What this means is not clear to me. What's an optimal destroy? Do you mean; a destroy that immediately leads to optimum value upon repair?

Limited Real-World Validation: The method has limited evaluation on real-world data, as the only non-synthetic dataset is from ML4CO, which is specifically designed for combinatorial optimization research. Additional real-world datasets from diverse applications could strengthen the paper's relevance. Algorithmic Complexity: The proposed sampling strategy introduces additional computational complexity, especially with tuning parameters like temperature decay and the neighborhood size. The increased complexity may limit SPL-LNS’s practicality for larger-scale real-world applications. Potential Overhead from Hindsight Relabeling: Although hindsight relabeling is intended to improve training data efficiency, it could add computational overhead to the training phase, particularly in scenarios with numerous variables and constraints.