Large Language Model-driven Large Neighborhood Search for Large-Scale MILP Problems

Authors: Huigen Ye, Hua Xu, An Yan, Yaoyang Cheng
Primary area: optimization
Keywords: Mixed Integer Linear Programming, Large Neighborhood Search, Large Language Model

Abstract:
Large Neighborhood Search (LNS) is a widely used method for solving large-scale Mixed Integer Linear Programming (MILP) problems. The effectiveness of LNS crucially depends on the choice of the search neighborhood. However, existing strategies either rely on expert knowledge or computationally expensive Machine Learning (ML) approaches, both of which struggle to scale effectively for large problems. To address this, we propose LLM-LNS, a novel Large Language Model (LLM)-driven LNS framework for large-scale MILP problems. Our approach introduces a dual-layer self-evolutionary LLM agent to automate neighborhood selection, discovering effective strategies with scant small-scale training data that generalize well to large-scale MILPs. The inner layer evolves heuristic strategies to ensure convergence, while the outer layer evolves evolutionary prompt strategies to maintain diversity.  Experimental results demonstrate that the proposed dual-layer agent outperforms state-of-the-art agents such as FunSearch and EOH. Furthermore, the full LLM-LNS framework surpasses manually designed LNS algorithms like ACP, ML-based LNS methods like CL-LNS, and large-scale solvers such as Gurobi and SCIP. It also achieves superior performance compared to advanced ML-based MILP optimization frameworks like GNN\&GBDT and Light-MILPopt, further validating the effectiveness of our approach.

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

Reviews and discussion:
<thread>
creation date:
1729387775394

thread_type:
official_review

<thread_object>
creator: reviewer_sbnr

<content>
summary:
This manuscript proposes a Dual-layer Self-evolutionary LLM-based method for heuristic generation. The experimental results demonstrate that LLM-based heuristic generation methods show promise compared to traditional heuristic generation methods.

strengths:
S1: This manuscript proposes an innovative approach by introducing a dual-layer structure for heuristic generation.

S2: This manuscript proposes an LLM-based method for ranking decision variables of MILP problems.

weaknesses:
W1: The proposed LLM-LNS lacks clarity in certain technical details, making it difficult to fully comprehend. For example, on Page 5, the authors say “These parents are then combined with evolutionary strategies, selected from the Outer Layer’s population of prompt strategies”. However, the criteria for selecting evolutionary strategies are not explained. Furthermore, on Page 6, the authors state that “underperforming strategies are pruned”. However, this manuscript fails to clearly define what is a poorly performing strategy. This manuscript relies heavily on textual explanations with insufficient mathematical formalization, making it difficult for readers to fully comprehend and reproduce the proposed LLM-LNS method. Including mathematical definitions, formulas, and pseudocode would greatly enhance clarity. Furthermore, the absence of open-source code compounds this issue, limiting both comprehensibility and reproducibility.

W2: The concept of using LLMs to evolve strategies resembles the approach in the prior study [1], while the notion of differential memory seems to align with another method from [2]. However, this manuscript does not clearly delineate the distinctions between the proposed LLM-LNS method and these prior studies. In addition, it would be more convincing to include experimental comparisons with these prior studies. 

W3: In Section 3.2, the authors state that “Initially trained on small-scale MILP problems, the agent learns effective strategies for selecting promising decision variables.” However, the manuscript lacks details regarding the training process of the LLM agent. For example, how many parameters does it contain? Is it fine-tuned on an existing open-source LLM (e.g., Llama) using MILP data?

W4: In Section 4.1, the experiments are conducted using only a single LLM (GPT-4o-mini), which raises concerns about the robustness of the proposed LLM-LNS method when applied to different LLMs. It is recommended to reference prior studies [3] and conduct experiments across multiple LLMs. In addition, in Section 4.2, can existing LLMs (e.g., Llama) be used to rank decision variables without requiring pretraining using MILP data? If so, why are they not included in comparisons with LLM-LNS?

W5: The lack of ablation studies further raises concerns about the effectiveness of certain submodules within LLM-LNS, such as Differential Memory. Conducting ablation studies would provide valuable insights into the contribution of each submodule.

W6: This manuscript is missing important details in some areas and contains grammatical errors. For example, in Table 1, the terms "Evolutionary Prompt," "Strategic Evolution," and "Directional Evolution" are not explained. Additionally, on Page 8, there is a grammatical error: “In the Appendix A B C D”. 


[1] Connecting large language models with evolutionary algorithms yields powerful prompt optimizers. In ICLR, 2024.

[2]  Large language models as hyper-heuristics for combinatorial optimization, arxiv, 2024.

[3] Evolution of heuristics: Towards efficient automatic algorithm design using large language model. In ICML, 2024.

questions:
Please refer to the weakness section.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730367723848

thread_type:
official_review

<thread_object>
creator: reviewer_bc3z

<content>
summary:
This article presents 1. Dual-layer Self-evolutionary LLM Agent and 2. Differential Memory for Directional Evolution to implement LLM as Hyper-heuristic on MILP.

strengths:
1. The results of the proposed method shown in the article is leading.
2. The proposed Dual-layer Self-evolutionary LLM Agent is novel and reasonable

weaknesses:
I have doubts mainly about the contribution of this paper. I cannot determine whether there is some over-claim in this paper.
1. This paper claims that the introduction of LLM-driven heuristic on LNS is an innovation at the application level. I wonder whether other comparative algorithms such as EoH cannot be similarly introduced to LNS.
2. This paper lacks ablation experiments. I have some doubts about the effectiveness of Differential Memory for Directional Evolution intuitively. I would like the authors to add ablation experiments to validate the contribution of the two components of this paper.

questions:
1. This paper lacks some clear experiments setting descripsion on Online Bin Packing and Travelling Salesman Problem (e.g. seemingly you use GLS for TSP), which can be very misleading.
2. As my biggest question: on LNS, why does the algorithm SCIP, which is considered to generate labels in [1], perform so poorly?
3. The authors should elaborate on whether they introduced a seed function (initial code for experts) thus introducing possible unfair comparisons. (I observe that the method proposed in this paper has an initial advantage in Figure 3).
4. As the proposed Differential Memory for Directional Evolution will increase the input length (token numbers), can you analyze the relationship between the number of input tokens or API cost and the optimization effect？
5. Please discuss the limitations of this paper.
[1]Huang, Taoan, et al. "Contrastive Predict-and-Search for Mixed Integer Linear Programs." Forty-first International Conference on Machine Learning.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730387845890

thread_type:
official_review

<thread_object>
creator: reviewer_a92q

<content>
summary:
This paper proposes to use LLMs to guide adaptive large neighborhood search, with the following three components (1) prompt evolution (2) heuristics evolution (3) differential memory that feeds back the fitness score from past generations. The authors evaluate the performance on online bin packing, traveling salesman and large scale MILP and show the performance improvement from a variety of baseline methods.

strengths:
- To my knowledge, there has not been works that combine LLMs with large neighborhood search based heuristics. So this can be regarded as a new task (although I have concern about the novelty given there has been works that combine LLMs with a lot of other heuristics and search algorithms for CO).
- The authors evaluate the performance of the algorithm on three sets of CO problems (online bin packing, traveling salesman, and large-scale MILP). The scope of evaluation (in terms of three different problem classes) seems to be satisfactory.
- I find using prompt evolution to prevent the search process from getting trapped in local optima interesting.

weaknesses:
- I find Figure 1 confusing. There are too many components in the illustration, and it’s hard to parse the relationship of the arrows from one component to another. I suggest the authors to improve the visualization of the pipeline (e.g. emphasize the important components, remove less important ones) to make it more clear.
- I find the paper lacking baseline comparisons. For example, I would like to see the performance of adaptive large neighborhood search (ALNS) with different heuristic scoring functions (not LLM designed). I also would like to see how each component of the LLM pipeline (prompt evolution, heuristic evolution, and differential memory) contributes to the final performance.
- For traveling salesman, the performance seems to be evaluated only on a small set of instances (5 instances). How is this set selected? I believe the authors need to evaluate on a larger set of instances to claim the performance improvement.
- I have slight concerns about the novelty of the proposed method. The three components used by the authors have all been proposed in previous works. While it is interesting to combine them together and show effectiveness, I’m concerned that the proposed methodology may not be novel enough.

questions:
- How large is the training set for each task? I may miss it, but it doesn’t seem to clear from reading the main paper.
- Why do the authors train on small-scale problems and generalize to larger problems? What would happen if the authors directly train on larger problems?
- Is the proposed method sensitive to what algorithm backbone the authors are using? e.g. instead of ALNS, would the proposed method perform well when combined with other search / decomposition methods, or LNS without the adaptive size?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730474899250

thread_type:
official_review

<thread_object>
creator: reviewer_vja9

<content>
summary:
This paper introduces a new dual-level heuristic design method based on LLMs and applies it to the development of large neighborhood search (LNS) heuristics for MILP. The proposed method shows promising results in packing problems and TSP, when compared to existing methods such as FunSearch and EoH. It successfully generates new heuristics that surpass traditional hand-crafted approaches in LNS.

strengths:
1. The dual-level framework incorporates both prompt evolution and directional evolution, enhancing heuristic design.
2. It introduces effective new heuristics specifically tailored for large neighbourhood searches in MILP. The results show good scalarization.

weaknesses:
1. The specific contributions of the newly introduced components in the dual-level framework remain unclear.
2. Additional experimental results are needed to further validate the effectiveness of the proposed method.

questions:
1. How do the individual components of the dual-level framework contribute to its overall performance? An ablation study is recommended.
2. How many repeated trials were conducted using the proposed method, EoH, and FunSearch on the tasks compared? How consistent are the results of the proposed method, considering that the initial seed heuristics appear to be hand-crafted?
3. What are the detailed settings for the Differential Memory in Directional Evolution? Are both thought directions and code directions utilized? Could you provide an illustrative example and discuss how these mechanisms impact the results?
4. Why are the settings for population size different between LNS tasks and combinatorial optimization tasks? How does changing the population size affect the outcomes within your framework?
5. What performance levels do FunSearch and EoH achieve on the LNS tasks? Are their results comparable to those of the proposed method?
6. What new insights have been gained from the application of LLM-designed heuristics in LNS for MILP, and how might these contribute to the field?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732522302522

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Global Response about Manuscript

comment:
We would like to sincerely thank all reviewers for their valuable and constructive feedback on our manuscript. Your insightful comments have greatly helped us improve the clarity, rigor, and comprehensiveness of our work. During the rebuttal phase, we have addressed the concerns raised by the reviewers, incorporated additional experiments, and strengthened the arguments supporting the effectiveness of our proposed method. We also deeply appreciate the reviewers who acknowledged the novelty and potential future impact of our approach after our initial rebuttal responses.

We are pleased to inform you that we have uploaded a revised version of the PDF manuscript, which includes substantial updates based on the feedback received. These updates are summarized in the table below. In the remaining time of the rebuttal phase, we will continue to refine and further enhance the manuscript and welcome any additional feedback from the reviewers.

| **Comment**                                                  | **Addition**                                                 | **Location**                                 |
| ------------------------------------------------------------ | ------------------------------------------------------------ | -------------------------------------------- |
| Reviewer vjA9 W1, Reviewer a92q W1                           | New overview of the proposed LLM-LNS framework               | Details in Method Section, Figure 1          |
| Reviewer vjA9 Q1, Reviewer a92q W2, Reviewer bC3Z W2, Reviewer SBNr W5 | Ablation Study of the Dual-Layer Self-evolutionary LLM Agent | Details in Appendix E                        |
| Reviewer vjA9 Q2                                             | Stability Evaluation of Multiple Runs                        | Details in Appendix F.1                      |
| Reviewer vjA9 Q4                                             | Impact of Population Size on Experimental Outcomes           | Details in Appendix F.2                      |
| Reviewer vjA9 Q5, Reviewer bC3Z W1                           | Performance Comparison with EoH on LNS Tasks                 | Details in Appendix F.3                      |
| Reviewer a92q W2                                             | Baseline Comparisons with Additional LNS Methods             | Details in Appendix D.5                      |
| Reviewer a92q W3                                             | Comprehensive Evaluation on TSPLib Instances                 | Details in Appendix F.4                      |
| Reviewer a92q Q1                                             | Datasets for Heuristic Evolution                             | Details in Appendix A.3                      |
| Reviewer a92q Q3                                             | Impact of the Backbone Algorithm on Performance              | Details in Appendix F.5                      |
| Reviewer bC3Z Q1 and Q3                                      | Experimental Settings for Algorithm Design                   | Details in Appendix A.4                      |
| Reviewer bC3Z Q5                                             | Limitations and Future Directions                            | Details in Appendix H                        |
| Reviewer SBNr W1                                             | Comprehensive revision of the Method section with additional formalizations | Details in the Method section and Appendix G |
| Reviewer SBNr W4                                             | Robustness of LLM-LNS with Different LLMs                    | Details in Appendix F.6                      |
| Reviewer SBNr W2F, Reviewer a92q Q1F                         | Comparison with ReEvo                                        | Details in Appendix F.7                      |
| Reviewer SBNr W4F                                            | Performance Comparison with EoH Using Different LLMs         | Details in Appendix F.8                      |
| Reviewer SBNr W4F                                            | Comparison with Standalone LLMs                              | Details in Appendix F.9                      |

We deeply value the reviewers' feedback and believe the revisions significantly enhance the quality and transparency of the manuscript. We look forward to addressing any further questions or comments to ensure the work meets the highest standards of clarity and rigor.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper proposed a large language model (LLM) driven large neighborhood search (LNS) method for large-scale Mixed-Integer Linear Program (MILP) problems. The core contribution is a dual-level framework, where the outer layer optimizes prompt strategies using differential evolution, while the inner layer generates heuristic strategies guided by the optimized prompts. The proposed method demonstrated good performance on three types of problems, including online bin packing, TSP, and large-scale MILPs.

Reviewers acknowledged the novelty of the proposed dual-level scheme and its good empirical performance. However, they have major concerns including 1) limited contribution since the proposed method combines existing techniques, 2) lacking of proper ablation study, and 3) unclear presentation. These concerns largely remains after rebuttal. Since 3 out of 4 reviewers are negative, I recommend rejection.