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

W6: This manuscript is missing important details in some areas and contains grammatical errors. Additionally, on Page 8, there is a grammatical error: “In the Appendix A B C D”.

R6: Thank you for your valuable feedback. We appreciate your detailed observations, which have helped us identify areas where the manuscript can be improved.

We have taken two steps to address the concerns regarding Table 1 and the related terminology. First, we revised the table by renaming "Evolutionary Prompt Strategy Evolution" to the more concise term Prompt Evolution for clarity and readability. Second, we added detailed explanations of the terms in the main text, clarifying that:

• Prompt Evolution refers to the outer-layer evolution mechanism that optimizes prompts through genetic operations like crossover and mutation, guiding the generation of inner-layer strategies and enhancing population diversity.
• Directional Evolution builds on differential evolution, where differences in parent fitness values guide the search process, ensuring a more efficient and targeted optimization.

These revisions highlight the specific roles these mechanisms play within our framework and how they address the limitations of prior works, such as FunSearch and EOH. By including these explanations in the main text, we have enhanced the clarity and accessibility of the manuscript.

As for the grammatical issue on Page 8 ("In the Appendix A B C D"), we are grateful for pointing out this oversight. We have revised the phrasing to the standard format, “In Appendices A to D.” Additionally, we conducted a comprehensive review of the manuscript to identify and correct any other grammatical or stylistic issues, ensuring precise and professional language throughout.

Thank you again for your meticulous review and constructive suggestions. These improvements have made the manuscript more polished and reader-friendly. If you have any further comments, we would be happy to address them.

References

[1] Guo Q, Wang R, Guo J, et al. Connecting Large Language Models with Evolutionary Algorithms Yields Powerful Prompt Optimizers[C]. The Twelfth International Conference on Learning Representations.

[2] Ye H, Wang J, Cao Z, et al. Reevo: Large language models as hyper-heuristics with reflective evolution[J]. arXiv preprint arXiv:2402.01145, 2024.

Regarding the second question, directly ranking decision variables using existing LLMs without employing our framework would correspond to the initial strategies generated by the LLM. As shown in Figure 2 of the main text, these initial strategies perform poorly compared to the optimized strategies produced by LLM-LNS. This is primarily because:

• LLMs lack domain-specific optimization knowledge and require iterative refinement to improve strategy quality.
• The LLM-LNS framework incorporates differential evolution and feedback mechanisms to guide the LLM, significantly enhancing the generated strategies.

In summary, the experiments confirm that our framework improves decision-variable ranking and optimization compared to standalone LLMs, with robustness across different LLMs. Thank you for your valuable suggestion, which has helped us strengthen our experimental evaluation. If you have further feedback, we would be happy to address it.

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.

R5: Thank you for your valuable suggestion. To address your concerns, we conducted ablation studies to analyze the contributions of key submodules within the LLM-LNS framework, including Differential Memory and the dual-layer structure.

From a theoretical perspective:

• The outer layer employs a differential evolution mechanism to optimize prompt strategies, enhancing the diversity of the search process and preventing stagnation in local optima.
• The inner layer, guided by the optimized prompts, leverages differential evolution to refine heuristic strategies, enabling faster convergence toward high-quality solutions.
• The Differential Memory mechanism facilitates directional evolution by learning from differences across multiple parent strategies, improving the efficiency and adaptability of the optimization process.

To empirically validate the contributions of these components, we conducted ablation experiments by progressively removing or isolating each submodule and observing the impact on performance. The results of these experiments, included in the updated manuscript, reveal the following:

1. Effect of Differential Memory: Removing the Differential Memory mechanism while retaining the dual-layer structure leads to a performance drop, particularly on large-scale datasets. For example, on the 10k_C500 dataset, the error rate increases from 0.39% (full framework) to 0.72%, indicating that Differential Memory is critical for guiding efficient and directional evolution, especially in complex search spaces.
2. Effect of the Dual-layer Structure: When the outer layer is removed, reducing the framework to a single-layer optimization process, performance degrades significantly. On the same 10k_C500 dataset, the error rate increases from 0.39% to 1.14%. This highlights the importance of prompt optimization in enhancing the diversity of strategies and enabling the inner layer to achieve better results.
3. Combined Effect: While individual components contribute significantly to performance, their combination achieves the most comprehensive improvement. For small-scale problems, such as the 1k_C100 dataset, the outer layer's diversity-enhancing strategies introduce some exploration overhead, resulting in slightly higher error rates compared to using the inner layer alone. However, for large-scale problems, the synergy between the outer and inner layers and Differential Memory ensures superior performance overall.

These results validate the effectiveness of the Differential Memory mechanism and the dual-layer structure while revealing their complementary roles in the optimization process. We plan to include the complete experimental results and analyses in the appendix of the updated manuscript to provide further clarity.

Thank you again for your suggestion, which has helped us better demonstrate the contributions of our method. We welcome any additional feedback or suggestions you may have.

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?

R3: Thank you for raising this important question. Regarding the training process of the LLM agent, we would like to clarify the specific methodology employed in our work. The core innovation of this paper lies in the proposed Dual-layer Self-evolutionary LLM Agent, which does not involve parameter-level fine-tuning of the large language model (LLM). Instead, it fully leverages the LLM’s contextual learning capability, i.e., Few-shot Prompting, to learn effective strategies for MILP problems.

In our framework, the LLM agent is trained by providing structured input information and a few examples of small-scale MILP problems within the prompt. These few-shot examples guide the LLM to generate heuristic strategies without requiring parameter updates. This approach avoids the need for model fine-tuning, relying instead on carefully designed prompts to elicit the LLM’s reasoning and generalization abilities. Since contextual learning depends on prompt design rather than parameter adjustment, the training process is efficient and easily transferable to different optimization problems.

The LLM used in our experiments (e.g., GPT-series models) contains billions of parameters, which are fixed during the pretraining phase. These parameters are learned from pretraining on large-scale general-purpose corpora and are not modified in our framework. Instead, our method embeds MILP-specific features into the context through prompt engineering, enabling the LLM to generate problem-specific strategies dynamically.

Furthermore, in the dual-layer structure:

• The outer layer optimizes the prompt through differential evolution, enhancing the efficiency and effectiveness of contextual learning.
• The inner layer, guided by the optimized prompt, generates heuristic strategies, demonstrating the adaptability of the LLM to MILP problems.

This combination of contextual learning and dual-layer optimization allows our framework to efficiently learn strategies on small-scale MILP problems and generalize to larger instances.

To avoid potential misunderstandings, we will add more details about the training process in the revised manuscript, explicitly distinguishing our use of contextual learning from parameter-level fine-tuning. Thank you again for your suggestion, which has helped us clarify the design choices behind our framework. If you have further feedback, we would be happy to address it.

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 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?

R4: Thank you for raising these concerns. To address the robustness of the LLM-LNS framework across different LLMs, we conducted additional experiments using various LLMs, including GPT-4o, GPT-4o-mini, DeepSeek, Gemini-1.5-Pro, and Llama-3.1-70B. The results on the 10k_C500 dataset are summarized in the table below:

The results demonstrate the following:

1. General Robustness: Despite significant performance differences between models, all tested LLMs achieved reasonable results within the LLM-LNS framework. This highlights the robustness of our dual-layer structure in adapting to different LLMs.
2. Performance Variations: GPT-4o consistently achieved the best results, followed by GPT-4o-mini and DeepSeek. Gemini-1.5-Pro and Llama-3.1-70B exhibited weaker performance. These differences are likely due to variations in model architecture and pretraining quality. The LLM-LNS framework, however, remains effective across all models.

These extended experiments validate the adaptability of our framework to multiple LLMs. The complete results and analysis will be included in the updated appendix of the manuscript.

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.

R2: Thank you for raising this important question about the novelty of our method. We have carefully compared the proposed LLM-LNS framework with the approaches described in [1] and [2], and we provide the following clarifications regarding the distinctions and innovations of our method:

First, the EvoPrompt method in [1] focuses on optimizing prompts for large language models (LLMs) using evolutionary algorithms (EA). Its primary objective is to treat the prompt itself as an optimization target, generating new prompts through crossover and mutation to iteratively improve performance. However, the scope of [1] is limited to prompt optimization and does not address the interplay between prompt optimization and strategy generation. In contrast, our LLM-LNS framework introduces a dual-layer co-evolutionary structure that integrates prompt optimization with heuristic strategy generation. Specifically, the outer layer optimizes prompt strategies via a differential evolutionary mechanism, which directly influences the direction of heuristic strategy evolution in the inner layer. Simultaneously, the optimization results of inner-layer strategies provide feedback to refine and prune outer-layer prompts. This bidirectional synergy allows LLM-LNS to dynamically balance diversity and convergence in complex optimization scenarios, significantly enhancing overall performance.

Second, the ReEvo method proposed in [2] introduces a short-term memory mechanism to reflect on and refine the relative performance of parent strategies. While this mechanism shares some conceptual similarities with our differential memory approach, there are fundamental differences in design and application. The short-term memory in [2] relies on pairwise comparisons of parent strategies, whereas our differential memory mechanism learns from differences across multiple parents, enabling the generation of more directional and effective evolutionary strategies. This multi-parent differential learning mechanism improves optimization efficiency and adaptability to complex search spaces, particularly for large-scale MILP problems. Moreover, while [2] focuses on heuristic strategy enhancement, our method combines differential memory with the dual-layer structure to achieve deeper integration between prompt optimization and strategy generation, resulting in a more comprehensive optimization framework.

To demonstrate the effectiveness of the components in our framework, we have conducted detailed ablation studies (as shown in R2 of the manuscript). These experiments validate the contributions of the dual-layer structure and differential memory mechanism to the overall performance of LLM-LNS. For example, removing the differential memory mechanism results in a noticeable drop in performance, particularly for large-scale MILP problems, which highlights its critical role in guiding directional evolution. Similarly, omitting the outer-layer prompt optimization significantly reduces the diversity of strategies, leading to slower convergence and suboptimal results. These findings further distinguish our method from [1] and [2], as the interplay between the dual-layer structure and differential memory is a unique aspect of our approach.

It is also worth emphasizing that LLM-LNS is the first framework to apply LLMs for automated LNS strategy discovery in large-scale MILP optimization. While [1] and [2] explore the combination of LLMs and evolutionary algorithms, their objectives and application domains differ significantly from ours: [1] focuses on prompt optimization, [2] emphasizes heuristic strategy refinement, and our work targets the automated design and optimization of LNS strategies for solving MILP problems with hundreds of thousands to millions of decision variables. This integration of LLM capabilities with large-scale optimization is a novel contribution that, to the best of our knowledge, has not been addressed in existing literature.

Thank you again for your valuable suggestion, which has helped us clarify the contributions and innovations of our method. We welcome any further feedback you may have.

Thank you for your thorough and insightful review of our work. We are encouraged by your recognition of the contributions and experimental achievements of our proposed framework. Your detailed comments and suggestions have been invaluable in refining the presentation and ensuring the robustness of our methodology. Below, we provide detailed responses to your comments and questions.

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.

R1: Thank you for pointing out these important issues. We recognize that the lack of clarity in describing key technical details may affect the comprehensibility and reproducibility of our proposed LLM-LNS framework. To address these concerns, we will provide more detailed explanations for the issues you have raised and include mathematical formalizations and pseudocode in the final version of the manuscript. Additionally, we commit to open-sourcing the complete codebase upon publication to further enhance transparency and reproducibility.

Regarding the criteria for selecting evolutionary strategies, our method constructs a probability distribution based on the fitness values of strategies within the population. Fitness values measure the performance of each strategy in achieving the optimization objective: the higher the fitness value, the better the strategy. Specifically, let the population contain n strategies, with fitness values ranked from highest to lowest as $f_1, f_2, \dots, f_n$. The probability of selecting the $i$-th strategy is calculated as:

$$P_i = \frac{1}{i + 1 + n}, \quad i = 1, 2, \dots, n$$

Here, $i$ represents the rank of the strategy (starting from 0), and $n$ is the population size. This ranking-based probability distribution ensures that high-fitness strategies are more likely to be selected, while retaining some randomness to allow lower-fitness strategies to participate, thereby enhancing population diversity. Using this mechanism, we probabilistically sample $m$ parent strategies from the population for crossover and mutation, generating new candidate strategies.

For the definition of poorly performing strategies, we follow standard evolutionary algorithm principles by treating strategies with lower fitness values as underperforming. After each generation of evolution, we manage the population to maintain a fixed size. Let the current population be $P = \{ s_1, s_2, \dots, s_n \}$, where each strategy $s_i$ has a fitness value $f(s_i)$. The goal is to construct a new population $P'$ such that:

• $P'$ size is minimized to $\min(\text{size}, |P|)$,
• Strategies with duplicate fitness values are removed,
• The highest-fitness strategies are retained.

Concretely, we first filter out invalid strategies (e.g., those with undefined fitness values), remove duplicates, and then rank strategies by fitness value, selecting the top $\text{size}$ strategies to form $P'$. This ensures that high-quality strategies are preserved while avoiding redundancy, thereby improving the overall quality and diversity of the population.

In our experiments, the fitness value of a strategy is determined by its optimization performance on small-scale training problems, measured as the average objective value across multiple instances. This fitness-driven selection and population management mechanism enables the LLM-LNS framework to balance exploration and exploitation during each generation, progressively improving the quality and diversity of strategies.

We will include the above mathematical details, formulas, and pseudocode in the revised manuscript to enhance clarity and rigor. Thank you again for your valuable feedback, which has been instrumental in improving the presentation of our work.

We sincerely thank you for your thoughtful and constructive feedback on our manuscript. Your comments have been invaluable in helping us identify areas for improvement and validate the effectiveness of our proposed framework. Below, we summarize our responses to your key concerns and the actions we have taken to address them:

W1F: The selection criteria and poorly performing strategies are only two examples of the issues I raised. There are still several undefined technical details in the manuscript.

R1: Thank you very much for your constructive feedback and for highlighting areas where the clarity and technical depth of our manuscript could be improved. We greatly appreciate your suggestions, which have allowed us to identify and address critical issues in our work, ultimately improving the overall presentation.

As mentioned in our Global Response, we have uploaded a revised version of the manuscript that incorporates significant updates to address the issues raised. Specifically, we have added more in-depth technical explanations to Sections 3.1.2, 3.2, and Appendix G, ensuring that the methodology is described with greater precision and depth. These updates aim to clarify key technical details and enhance the comprehensibility of the proposed method.

Regarding the overlap in the definition of the variable k in Appendix A, we have corrected this inconsistency in the revised manuscript. To avoid confusion, we have introduced a new variable h to represent "the number of top-performing heuristic strategies used to evaluate each prompt strategy," while retaining k exclusively as the neighborhood size in ALNS. This revision ensures that each variable is clearly and consistently defined based on its specific context.

We are still actively refining this version of the manuscript to further improve its clarity and technical rigor. Your feedback has been instrumental in helping us identify these critical areas for improvement, and we warmly welcome any additional suggestions you may have. Thank you again for your valuable input, which has been essential in enhancing the quality of our work.

Q2: 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?

A2: Thank you for your question. Training on small-scale problems and generalizing to larger ones is motivated by practical constraints. Real-world applications often lack diverse large-scale MILP data, as such instances are proprietary, domain-specific, and computationally expensive to solve. Additionally, training on large-scale problems involves significant computational costs, making it less feasible in practice. Hence, our approach reflects realistic scenarios in terms of data availability and resource limitations.

Our results (e.g., Table 5) show that strategies trained on small-scale problems generalize effectively to larger instances, consistently outperforming existing methods. For example, our model trained on instances with tens of thousands of variables demonstrates robust performance on problems with hundreds of thousands or even millions of variables. This success is attributed to our dual-layer self-evolutionary mechanism and differential memory, which enable scalability.

Direct training on larger problems could theoretically yield better results if sufficient resources were available. However, the scarcity of large-scale data and high computational overhead make this impractical in most scenarios. We will explore this as an avenue for future research. Thank you for your insightful question.

Q3: 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?

A3: Thank you for raising this important question. Our study focuses on solving large-scale MILP problems, where heuristic methods play a critical role due to the complexity of the problem space. Among these methods, LNS has shown significant advantages in scalability and efficiency, particularly for large-scale problems. This is why we chose ALNS, a variant of LNS with adaptive neighborhood size adjustment, as the backbone of our framework. ALNS dynamically balances exploration and exploitation by adjusting neighborhood sizes, making it more effective than non-adaptive LNS methods, which often struggle with local optima in large-scale problems.

To further validate this choice, we conducted experiments replacing ALNS with non-adaptive LNS in our framework. The results, shown in the table, indicate that ALNS consistently outperforms non-adaptive LNS across all tested MILP instances. This demonstrates that the adaptive mechanisms in ALNS are critical for leveraging the full potential of our framework.

We will include detailed experimental comparisons in the appendix of the revised paper to highlight the impact of the backbone algorithm. Thank you again for your suggestion, which has helped us further evaluate the robustness of our method.

References

[1] Berthold T. Primal heuristics for mixed integer programs[D]. Zuse Institute Berlin (ZIB), 2006.

[2] Nair V, Alizadeh M. Neural large neighborhood search[C]. Learning Meets Combinatorial Algorithms at NeurIPS2020. 2020.

[3] Danna E, Rothberg E, Pape C L. Exploring relaxation induced neighborhoods to improve MIP solutions[J]. Mathematical Programming, 2005, 102: 71-90.

[4] Ye H, Wang H, Xu H, et al. Adaptive constraint partition based optimization framework for large-scale integer linear programming (student abstract)[C]. Proceedings of the AAAI Conference on Artificial Intelligence. 2023, 37(13): 16376-16377.

[5] Song J, Yue Y, Dilkina B. A general large neighborhood search framework for solving integer linear programs[J]. Advances in Neural Information Processing Systems, 2020, 33: 20012-20023.

[6] Liu F, Xialiang T, Yuan M, et al. Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model[C]. Forty-first International Conference on Machine Learning. 2024.

[7] Romera-Paredes B, Barekatain M, Novikov A, et al. Mathematical discoveries from program search with large language models[J]. Nature, 2024, 625(7995): 468-475.

[8] Kool W, Van Hoof H, Welling M. Attention, learn to solve routing problems![J]. arXiv preprint arXiv:1803.08475, 2018.

3. Enhanced Adaptability and Generalization Compared to Existing Methods: Compared to methods such as EOH and FunSearch, our framework offers greater adaptability and generalization:
   • Existing methods often rely on single-layer strategy generation or fixed evolution rules, which limit their ability to dynamically adjust to the problem structure or scale. In contrast, our dual-layer framework combines outer-layer prompt evolution and inner-layer heuristic refinement to achieve coordinated optimization.
   • The integration of differential memory enables our framework to learn from past experiences, further enhancing its robustness and scalability.
4. Experimental Validation and Superior Performance: Our experiments demonstrate the effectiveness of the proposed framework across a diverse set of tasks, including both combinatorial optimization problems (e.g., TSP and bin packing) and large-scale MILP instances. The results show that:
   • On small-scale problems, our method achieves faster convergence and higher solution quality compared to baselines.
   • On large-scale MILP problems, our framework significantly outperforms state-of-the-art methods such as EOH and Random-LNS, demonstrating superior scalability and generalization capabilities. These results not only validate the effectiveness of the dual-layer framework but also highlight the critical role of differential memory in improving optimization performance.

Summary of Contributions: The novelty of our work lies not just in combining existing ideas but in the creation of a new framework tailored to the challenges of large-scale MILP problems.

We appreciate your feedback, which has allowed us to better articulate the unique contributions of our work. We will strengthen the description of these innovations in the revised manuscript to more clearly highlight their significance. If you have further suggestions, we would be happy to incorporate them. Thank you again for your valuable comments.

Q1: How large is the training set for each task? I may miss it, but it doesn’t seem to be clear from reading the main paper.

A1: Thank you for raising this point. We acknowledge that the details regarding the training set size for each task could be clarified further. In the revised version of our paper, we will include these details in the appendix for greater transparency. Below is a summary of the training set size for each task:

1. Combinatorial Optimization Problems (e.g., Bin Packing and Traveling Salesman Problem): To ensure a fair comparison with state-of-the-art methods (e.g., EOH), we adopted the same training data configurations as those used in EOH:
   • Bin Packing: The training set consists of 5 instances, each containing 5,000 items generated from a Weibull distribution, covering a wide range of item counts and container capacities.
   • TSP: The training set includes 64 randomly selected instances from the TSP100 dataset, as used in EOH. These instances are designed to represent a variety of problem structures and complexities.
2. MILP Problems: For MILP tasks, we followed a similar approach to the bin packing problem, using a small-scale training set to enable generalization to larger problems:
   • The training set consists of five small-scale MILP problems, each containing approximately tens of thousands of decision variables and linear constraints. Notably, our method, after training on these smaller instances, successfully generalizes to much larger MILP problems with hundreds of thousands to millions of decision variables, demonstrating its scalability and robustness.

We will include additional details in the revised manuscript's appendix, specifying the sources, sizes, and configurations of the training datasets for each task to enhance the paper's clarity and completeness.

Thank you again for your valuable suggestion, which has prompted us to improve the presentation of our experimental setup. If you have further feedback or additional questions, we would be happy to address them.

W3: For the traveling salesman problem (TSP), 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.

R3: Thank you for pointing this out and for your valuable suggestion. The traveling salesman problem (TSP) is a canonical combinatorial optimization problem, with effective baseline methods including EOH [6], FunSearch [7], and Attention Model [8]. Recent studies [6] have demonstrated that EOH is one of the best-performing methods for TSP, often surpassing other approaches. To ensure fairness and consistency with prior work, we initially followed the experimental settings of EOH and evaluated our method on the same set of test instances.

In response to your suggestion, we have expanded the scope of our experiments to include all 87 instances from the TSPLib benchmark. This comprehensive evaluation allowed us to better assess the generalization capabilities of our method. As shown in the updated results, our method outperforms EOH on 43 instances, matches EOH on 39 instances, and performs slightly worse than EOH on only 5 instances. On average, the gap between our approach and the best-known solutions improves by approximately 10% compared to EOH, further confirming the superiority of our method.

For example, as highlighted in the table below:

• On the pr439 instance, the gap decreases from 2.80% (EOH) to 1.97% (Ours).
• On the u574 instance, the gap decreases from 2.85% (EOH) to 1.38% (Ours).

These results demonstrate the strong generalization ability of our method across TSP instances of varying sizes and structures.

Q4: 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.

R4: Thank you for your insightful feedback and for raising concerns about the novelty of our proposed method. While our work builds upon ideas from prior research, the core innovations lie in the targeted improvements and deep integration of these ideas to address the unique challenges of solving large-scale MILP problems. Below, we provide a detailed explanation of the novelty and contributions of our method:

1. A Dual-Layer Self-Evolutionary Framework for Large-Scale MILP Problems: The primary focus of our work is solving large-scale MILP problems, for which we propose a dual-layer self-evolutionary framework driven by large language models (LLMs). This framework is designed to address two critical objectives in optimization algorithms—diversity and convergence—by introducing two distinct but complementary layers:
   • The outer layer enhances diversity by optimizing prompt strategies using a differential evolution mechanism, ensuring that the search process explores a broader solution space and avoids local optima.
   • The inner layer accelerates convergence by generating heuristic strategies based on the optimized prompts and refining them through differential evolution. This dual-layer design is a significant departure from existing methods, which typically rely on single-layer strategy generation or fixed evolutionary rules. This allows our framework to adaptively balance diversity and convergence, a key requirement for large-scale MILP problems.
2. Differential Memory for Directional Evolution: A key innovation of our method is the introduction of differential memory for directional evolution, which dynamically adjusts the strategy generation process based on historical fitness feedback. By feeding the fitness values of parent strategies back into the LLM, our framework enables the generation of more effective strategies that align with learned improvement directions. This mechanism leverages the memory capabilities of LLMs to optimize evolutionary paths, significantly improving the efficiency and quality of strategy generation. Unlike existing methods, which typically apply static or fixed evolutionary rules, our directional evolution mechanism ensures a more targeted and adaptive optimization process.

W2: 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.

R2: Thank you for your valuable suggestions. To address the concerns regarding baseline comparisons, we expanded our experiments to include additional ALNS methods with different heuristic scoring functions. Specifically, we incorporated Least-Integral[1], Most-Integral[2], and RINS[3], which are classical scoring functions commonly used in ALNS, alongside the state-of-the-art methods ACP [4] and Random-LNS [5]. According to recent studies [4], ACP and Random-LNS are considered the most effective LNS methods, which is why the initial design of our experiments focused on these baselines.

From the results in Table 1, it is evident that the newly added ALNS baselines (Least-Integral, Most-Integral, and RINS) perform worse than ACP and Random-LNS, and they also perform worse our proposed LLM-LNS. For example, on the SC₁ problem(a minimization task), our method achieves an objective value of 15802.7, compared to 16140.6 for Random-LNS, 17672.1 for ACP, and 22825.3 for Least-Integral. This trend is consistent across all MILP tasks, highlighting the advantage of our dual-layer framework and its ability to better balance diversity and convergence.

To evaluate the contribution of each component in the LLM pipeline (prompt evolution, heuristic evolution, and differential memory), we conducted ablation studies. As shown in Table 2, we progressively added components to the baseline EOH method:

1. Adding Differential Evolution alone significantly improves performance on small-scale tasks. For instance, on the 1k_C100 dataset, the error decreases from 4.48% to 2.64%, demonstrating the impact of differential evolution on accelerating convergence.
2. Adding the Dual-Layer Structure further enhances performance on large-scale tasks. For example, on the 10k_C500 dataset, the error decreases from 0.97% to 0.39%, showcasing the role of prompt evolution in improving generalization and diversity.
3. The full method (LLM-LNS) combines these components, achieving the best overall performance across tasks.

These results demonstrate that each component of the LLM pipeline makes a distinct and meaningful contribution to the overall performance. The combination of prompt evolution, heuristic evolution, and differential memory ensures both diversity and convergence, enabling our method to consistently outperform baselines.

We will include these additional experimental results and analyses in the revised manuscript to substantiate the advantages of our method. Thank you again for your insightful suggestions, which have allowed us to further enhance the depth and rigor of our experiments.

Thank you for your insightful review and for recognizing the contributions of our proposed framework and its experimental outcomes. We are especially grateful for the constructive feedback and questions you have raised, as they have helped us identify areas for further clarification and enhancement. Below, we provide a detailed point-by-point response to address your concerns.

W1: 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 improve the visualization of the pipeline (e.g., emphasize the important components, remove less important ones) to make it clearer.

R1: Thank you for your valuable feedback on Figure 1. We appreciate your suggestion and have redesigned the framework diagram to more clearly illustrate the structure and workflow of the dual-layer self-evolutionary mechanism. In the updated figure, we have removed unnecessary lines and emphasized the relationships between key components to make the visualization more concise and intuitive.

The core innovation of our framework lies in the introduction of the dual-layer self-evolutionary mechanism. The outer layer is responsible for optimizing prompt strategies using a differential evolution mechanism. It generates diverse prompts to guide the search process in the inner layer. Through operations such as population initialization, crossover, mutation, and fitness evaluation, the outer layer dynamically optimizes the prompt strategies, ensuring the diversity of the search process. This design prevents the search from getting trapped in local optima and enhances the framework's generalization ability on unseen instances.

The inner layer, guided by the prompts generated by the outer layer, further optimizes solutions to specific problems. The inner layer also incorporates a differential evolution mechanism for heuristic strategies, which accelerates convergence during problem-solving. While the outer layer ensures diversity, the inner layer focuses on fast convergence under the guidance of the currently optimized prompt. Together, the two layers collaborate to build an efficient and robust search framework.

Our experimental results demonstrate that this dual-layer design significantly improves the efficiency of solving large-scale MILP problems. The diversity ensured by the outer layer and the fast convergence facilitated by the inner layer complement each other, resulting in superior optimization performance.

We plan to add detailed explanations of the components in both layers to the main text and clarified the specific workflows in the updated framework diagram. Additionally, we will include experimental analyses in the appendix to demonstrate the contributions of each component to the overall performance. Thank you again for your suggestion, which has helped us improve the clarity and presentation of our framework. We hope the updated version better communicates the design principles and innovations of our approach. We welcome any further feedback you may have.

Thank you for the detailed rebuttal and the additional experiments provided. I have read the authors’ responses here and also their responses to other reviewers. I still have the following concerns.

1. I concern about the limited amount of insights this paper can provide to future readers. Specifically, LNS has been long proven to be an effective heuristics for large scale optimization and there has been many machine learning methods that aim to improve LNS. Hence, the idea of using learning to improve large scale optimization has been successfully demonstrated in previous literature. Furthermore, the success of LLM to improve many metaheuristics for combinatorial optimization has also been demonstrated in previous literature (such as EOH and ReEvo). Given this, I find it not surprising that LLM can provide better score functions for LNS. Hence, I’m concerned about the amount of research insights that this paper can offer to the community.

2. I appreciate that the authors provide a clarification of their contribution, but my concern regarding the novelty of the paper remains, as the main components of this framework (algorithm evolution, LLM + meta heuristics, and prompt evolution) all have appeared in the previous literature (although they may appear in separate works). I have the concern that combining these idea as a joint paper is not sufficiently novel. Also, as a minor comment, based on the authors’ newly provided ablation on the different components, I’m slightly worried that the improvement from the basic model (EOH) does not seem to be sufficiently large, especially given the substantial complexity introduced with the added components on top of EOH.

3. (Minor) Data distribution. Given the small number of training instances that are used for prompting TSP and MILP, I have doubt about whether the small set of training instances is sufficient to cover realistic CO problems.

Question:

• After reading the authors’ response to other reviewers, I wonder how does this method compare with ReEvo in terms of the actual performance?
• I’m surprised that CL-LNS (Huang et al.) perform poorly on the large scale MILP dataset. I checked Huang et al.’s paper and it seems like in their paper, the reported performance is significantly better than Random LNS. Can the authors comment on why their benchmarked results is so much worse than those reported in Huang et al.? Is it a different in the MILP data distribution? How would the result look like if the authors benchmark on the MILP distribution used in Huang et al.?
• Can the authors comment on in what situation end-to-end learning is needed for improving LNS, and in what situation prompting LLM as the score function is already sufficient?

Another comment: I just realized that the authors claim Random LNS (Song et al.) as the SoTA LNS method. I believe this does not entirely reflect Song et al.’s paper, as a major component of their paper is to introduce a learning method to improve upon the Random LNS baseline. I think the authors may need to modify the description of Random LNS to at least not claim that it is the SoTA method for LNS.

Thank you very much for your thoughtful feedback and for taking the time to review our rebuttal and additional experiments. We deeply appreciate your detailed evaluation of our work and your valuable comments, which have helped us refine our contributions and clarify the positioning of our research within the broader context of the field.

We understand your concerns regarding the insights, novelty, and experimental setup of our work, and we have provided detailed responses to each point raised. Specifically, we address questions about the insights our method offers to the research community, the novelty of integrating various components in our framework, the data distribution used for training and testing, and how our approach compares to related methods such as ReEvo and CL-LNS. Additionally, we have clarified the description of Random LNS to avoid any potential misrepresentation of its status as a baseline.

Below, we provide detailed responses to each of your comments and questions. We hope these answers will address your concerns and further highlight the contributions and significance of our work.

C1: I concern about the limited amount of insights this paper can provide to future readers. Specifically, LNS has been long proven to be an effective heuristics for large scale optimization and there has been many machine learning methods that aim to improve LNS. Hence, the idea of using learning to improve large scale optimization has been successfully demonstrated in previous literature. Furthermore, the success of LLM to improve many metaheuristics for combinatorial optimization has also been demonstrated in previous literature (such as EOH and ReEvo). Given this, I find it not surprising that LLM can provide better score functions for LNS. Hence, I’m concerned about the amount of research insights that this paper can offer to the community.

R1: Thank you for your thoughtful evaluation of our work. We fully understand your concerns regarding the novelty and insights this paper can provide to the research community. In response, we would like to emphasize that the primary contributions of this paper lie in the innovative design of our dual-layer agent architecture and its application to solving large-scale MILP problems.

LNS has indeed been widely recognized as an effective heuristic method for large-scale optimization problems. Its core mechanism involves destroying and repairing parts of the current solution to efficiently explore large neighborhoods. However, the performance of LNS heavily depends on the design of neighborhood selection strategies. Traditional methods often require extensive expert knowledge and suffer from cold-start issues, where the absence of prior knowledge significantly limits search efficiency. In recent years, machine learning (ML) techniques, such as reinforcement learning and imitation learning, have been integrated into LNS to automate neighborhood selection strategies. However, these ML+LNS methods exhibit notable limitations when addressing large-scale problems. For example, reinforcement learning methods typically converge slowly in the vast search space of MILP problems, while imitation learning approaches rely on substantial amounts of high-quality labeled data, which are computationally expensive to generate. As a result, both traditional handcrafted methods and existing ML+LNS methods struggle to perform well on large-scale MILP problems.

In this paper, we propose a dual-layer agent architecture, which fundamentally differs from existing frameworks such as EOH and ReEvo. Unlike EOH's single-layer design that directly generates heuristic strategies or ReEvo's reflection-based evolutionary mechanism, our method introduces a dual-layer structure to achieve a novel form of collaborative optimization. The outer layer and inner layer in our framework are tightly integrated to dynamically enhance both search diversity and solution convergence. This dual-layer design enables our method to overcome the limitations of existing approaches, such as EOH’s insufficient exploration diversity and ReEvo’s instability due to hallucination issues.

Building on this dual-layer structure, we demonstrate its potential by applying it to Local Neighborhood Search (LNS), opening a new direction for improving LNS in large-scale optimization problems. To the best of our knowledge, this is the first work to integrate Large Language Models (LLMs) into the LNS framework. Through its iterative feedback loop, our dual-layer mechanism achieves a dynamic balance between exploration and exploitation, effectively addressing the bottlenecks faced by traditional methods in large-scale optimization.

In summary, the input length in our method remains similar to that of traditional approaches but achieves better optimization effects through the introduction of directional evolution. This highlights the efficiency and effectiveness of the proposed mechanism. We will expand on this analysis in the revised manuscript to further clarify the relationship between token numbers, API costs, and optimization performance. Thank you for your valuable suggestion, and we welcome any additional feedback you may have.

Q5: 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.

A5: Thank you for raising this important question. While the proposed dual-layer self-evolutionary framework has demonstrated strong performance in solving large-scale MILP problems, we acknowledge that the method has certain limitations that warrant further exploration and improvement. Below, we discuss these limitations in detail:

First, while the framework shows good generalization ability on MILP and certain combinatorial optimization problems, it is currently tailored to specific optimization scenarios. The design is primarily focused on MILP and does not directly extend to other types of optimization tasks, such as nonlinear optimization or dynamic optimization problems. Developing a more general agent structure that can adapt to a wider range of optimization algorithms and tasks remains an open challenge. In the future, we aim to explore more modular and flexible designs to enhance the adaptability of the framework for solving diverse and complex optimization problems.

Second, the current method leverages the generative capabilities of large language models (LLMs) and evolutionary mechanisms for heuristic strategy design. However, it does not fully incorporate domain knowledge or classical optimization expertise into the framework. In practical optimization tasks, domain-specific knowledge and traditional optimization techniques (e.g., heuristic rules or mathematical programming methods) often play a critical role. A key area for future work is to explore how to effectively integrate the generalization capabilities of LLMs with optimization domain knowledge to create more efficient and robust algorithms. Such integration could not only improve computational efficiency but also reduce the resource overhead for solving ultra-large-scale problems.

Finally, computational resource constraints remain a practical challenge for solving large-scale problems. Although the proposed framework demonstrates good scalability, solving ultra-large-scale instances still requires significant computational time and hardware resources, which may limit its applicability in resource-constrained environments. Future research could focus on optimizing the computational complexity of the algorithm or designing more efficient resource allocation strategies to address these challenges.

We will include a detailed discussion of these limitations in the revised manuscript, along with possible directions for future improvements. Thank you again for your valuable suggestion, which has helped us better reflect on the applicability and potential of our method. If you have additional feedback, we would be happy to address it.

References

[1] Huang T, Ferber A M, Zharmagambetov A, et al. Contrastive Predict-and-Search for Mixed Integer Linear Programs[C]. Forty-first International Conference on Machine Learning.

[2] Ye H, Wang H, Xu H, et al. Adaptive constraint partition based optimization framework for large-scale integer linear programming (student abstract)[C]. Proceedings of the AAAI Conference on Artificial Intelligence. 2023, 37(13): 16376-16377.

[3] Ye H, Xu H, Wang H. Light-MILPopt: Solving Large-scale Mixed Integer Linear Programs with Lightweight Optimizer and Small-scale Training Dataset[C]. The Twelfth International Conference on Learning Representations.

Thus, while SCIP remains a reliable solver for small-scale problems, its limitations become apparent when applied to large-scale MILP instances, as studied in this paper. Our proposed LLM-LNS method is specifically designed to address the challenges of large-scale problems, leveraging the dual-layer optimization framework to achieve superior performance both in terms of solution quality and computational efficiency.

We will expand on this discussion in the revised manuscript, including a detailed analysis of the problem scale differences and the limitations of SCIP in large-scale settings. Thank you again for your valuable question, which has helped us provide a clearer explanation of SCIP’s performance in our experiments.

Q3: 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).

A3: Thank you for your insightful question. In the dual-layer framework proposed in this paper, the outer layer optimizes prompt strategies via differential evolution to enhance diversity, while the inner layer refines heuristic strategies to accelerate convergence. During the initialization of heuristic strategies, we utilized initial code generated automatically by the large language model (LLM). However, no expert-written code or prior knowledge was manually introduced. Therefore, the comparisons in this paper are not affected by the use of any expert code, ensuring fairness.

In the experiments (e.g., Figure 3), the randomness inherent in LLM outputs leads to slight variations in the quality of the generated initial code across different runs. This randomness can cause fluctuations in initial performance. As shown in Figure 4 (red area), despite differences in initial code quality, our dual-layer self-evolutionary mechanism effectively compensates for these variations through the collaborative optimization of the outer and inner layers, resulting in superior final performance. In contrast, methods like EOH are more sensitive to the quality of the initial code. When the initial code performs poorly (e.g., Figure 3, blue area), EOH struggles to improve performance through the evolutionary process, leading to less stable optimization results and weaker overall performance.

This observation highlights that our framework is less dependent on initial code quality compared to existing methods. The dual-layer structure not only ensures diversity but also achieves rapid convergence, making the optimization process more robust and reliable, even when starting with suboptimal initial code generated by the LLM.

To further clarify, we will include additional details in the appendix of the revised manuscript about the experimental setup and the process of generating the initial code, to avoid any potential misunderstandings. Thank you for your valuable suggestion, which has helped us better articulate the strengths of our method. If you have further feedback, we welcome your continued input.

Q4: 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?

A4: Thank you for raising this important point. The proposed Differential Memory for Directional Evolution is implemented through a prompt-based mechanism. Specifically, this mechanism introduces fitness values of individual strategies into the prompt, enabling the large language model (LLM) to learn how to improve weaker strategies toward better-performing ones. This allows the optimization process to become more directional and efficient.

In traditional evolutionary methods, the input length primarily consists of the parent strategies and some descriptive prompt instructions. Our approach extends this by appending the fitness values of each parent strategy to the prompt. These fitness values guide the LLM in generating new strategies by learning from the differences between weaker and stronger parents. Importantly, this addition does not significantly increase the input length, as the fitness values are concise numerical descriptors. When the number of parents remains the same, the overall input length in our method is comparable to that of the baseline methods.

The results of our ablation study (as shown in R2) demonstrate that the Differential Memory for Directional Evolution significantly enhances optimization performance. By incorporating fitness feedback through the prompt, our method achieves more effective and targeted exploration of the solution space, leading to superior outcomes compared to the baseline methods that lack this mechanism.

Interestingly, while the full method (combining both components) achieves the best overall performance, it does not always outperform single-component models on small-scale problems. For instance, the error rate on the 1k_C100 dataset is 3.58% with the full method, slightly higher than the 2.64% achieved with only differential evolution. This can be attributed to the outer layer's focus on diversity, which may introduce overhead on smaller problems where rapid convergence is more critical. However, on larger problems, the synergy between diversity and convergence leads to superior results.

We have included detailed results and analyses in the appendix of the revised manuscript. These findings validate the complementary roles of the dual-layer structure and differential memory, as well as their combined effectiveness in tackling problems of varying scales and complexities. Thank you again for your suggestion, which has helped us better demonstrate the contributions of our method.

Q1: This paper lacks some clear experiment setting descriptions on Online Bin Packing and Travelling Salesman Problem (e.g., seemingly you use GLS for TSP), which can be very misleading.

A1: Thank you for highlighting this important point. Regarding the experimental settings for the Online Bin Packing (BP) and Travelling Salesman Problem (TSP), we strictly followed the experimental configurations used in EOH. For the TSP specifically, we employed Guided Local Search (GLS) as the heuristic strategy to be explored. GLS operates by introducing perturbations and dynamically adjusting the objective function to help the local search escape from local optima, thereby enabling a broader exploration of the solution space. This approach has demonstrated strong adaptability and effectiveness in solving combinatorial optimization problems.

To improve the clarity and reproducibility of our experiments, we will include additional details in the appendix of the revised manuscript. This will cover the design of the training data, the local search operators used, the implementation details of GLS, and the parameter settings for both BP and TSP. We will also provide a more complete description of the training datasets to avoid any potential misunderstanding of the experimental configurations.

Thank you again for pointing this out. Your suggestion has helped us further refine the experimental section of the paper, and we welcome any additional feedback you may have.

Q2: As my biggest question: on LNS, why does the algorithm SCIP, which is considered to generate labels in [1], perform so poorly?

A2: Thank you for raising this important question. Our study focuses on solving large-scale MILP problems, where the performance of SCIP is indeed limited. As noted in prior work such as [1], SCIP is a highly effective open-source solver for small-to-medium-scale problems, particularly when the number of variables and constraints is manageable. Its efficiency in these cases is largely attributed to its optimized branch-and-bound strategies and pruning techniques. However, as the problem size grows significantly, SCIP’s performance declines due to limitations in memory management and computational resource requirements.

The scale of the problems in our experiments is much larger than those in [1]. For example, the problem instances in [1] typically involve thousands of decision variables and constraints, whereas our tests focus on problems with hundreds of thousands to millions of variables and constraints. For such large-scale problems, SCIP often struggles to explore a sufficient portion of the solution space within a reasonable computational time, leading to suboptimal results.

Additionally, SCIP’s ability to generate high-quality labels in small-scale problems relies on its carefully engineered optimization strategies, such as advanced branching heuristics. However, for large-scale problems, the size of the branch-and-bound tree grows exponentially with the problem size, making it significantly harder for SCIP to effectively employ these strategies. Consequently, its performance deteriorates in terms of both solution quality and efficiency[2, 3].

We greatly appreciate your careful review of our manuscript and your recognition of the novelty and performance of our proposed framework. Your thoughtful questions and constructive suggestions have been immensely helpful in identifying ways to improve the clarity and comprehensiveness of our work. In the following, we provide detailed responses to address the issues you have raised.

W1: 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.

R1: Thank you for your question. The proposed method is a framework specifically designed for solving large-scale MILP problems. Comparative algorithms such as EoH and FunSearch are primarily designed for strategy discovery in combinatorial optimization problems. To ensure fairness and representativeness, we incorporated EoH into our framework (EoH-LNS) as a primary baseline for comparison with our LLM-LNS method.

We evaluated both methods on standard combinatorial optimization problems, such as the SC problem (a minimization task), using instances with 200,000 (SC₁) and 2,000,000 (SC₂) decision variables and constraints. The experimental results show that while EoH-LNS performs well, our LLM-LNS method consistently outperforms it. For example, on the SC₁ dataset, our method improves average performance by 1.67%, and on the SC₂ dataset, the improvement reaches 9.20%. These results demonstrate the superior capability of our framework in addressing the challenges of large-scale MILP problems.

The superior performance of LLM-LNS is attributed to its dual-layer self-evolutionary mechanism and differential evolution strategy, which balance diversity and convergence more effectively than EoH. While EoH can technically be adapted to LNS frameworks, it lacks the adaptive optimization capabilities inherent to our LLM-driven approach.

We plan to include additional experimental results, including tests applying FunSearch, in the appendix of the revised manuscript to further validate the advantages of our method. Thank you again for your insightful suggestion, which has provided us with valuable direction for further improving our work.

W2: 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.

R2: Thank you for your valuable suggestion. To analyze the contributions of the key components in our framework, including the dual-layer structure and differential memory for directional evolution, we conducted ablation experiments to validate their effectiveness.

The outer layer focuses on enhancing diversity through the evolution of prompt strategies, preventing the search process from getting stuck in local optima. The inner layer, guided by these prompts, accelerates convergence by refining heuristic strategies with differential evolution. The differential memory mechanism further improves the efficiency of strategy optimization by leveraging historical feedback to adjust the evolutionary direction dynamically.

As shown in the ablation study results, both components contribute significantly to the overall performance:

1. Adding the differential evolution mechanism alone improves performance on small-scale problems by accelerating convergence. For example, on the 1k_C100 dataset, the error rate decreases from 4.48% to 2.64%, demonstrating the effectiveness of this mechanism in improving solution quality.
2. Incorporating the dual-layer structure further enhances the diversity of the search process, leading to improvements on large-scale problems. On the 10k_C500 dataset, the error rate decreases from 0.97% to 0.39%, showing the importance of prompt evolution in handling large and complex problems.

Q1: How do the individual components of the dual-level framework contribute to its overall performance? An ablation study is recommended.

A1: Thank you for your valuable suggestion. To analyze the contributions of each component in the dual-level framework, we have conducted additional theoretical and experimental analyses.

From a theoretical perspective, the outer layer optimizes prompt strategies using a differential evolution mechanism, which enhances the diversity of the search process and avoids local optima. The inner layer, on the other hand, leverages differential evolution to rapidly optimize heuristic strategies, significantly improving convergence. The synergy between the two layers ensures both diversity and efficiency in the search process.

To empirically validate the impact of these two components on overall performance, we plan to supplement the manuscript with an ablation study, with results included in the updated PDF. In these experiments, we progressively incorporated the differential evolution mechanism and the dual-layer structure into the baseline method (EOH) and observed their effects on performance improvement.

The experimental results show the following:

1. Adding only the differential evolution mechanism significantly improves performance on small-scale test data. For example, on the 1k_C100 dataset, the error rate decreases from 4.48% to 2.64%, demonstrating that the differential evolution mechanism efficiently accelerates convergence through more effective crossover and mutation strategies.
2. Incorporating the dual-layer structure further enhances the diversity of the search process via prompt evolution in the outer layer. This leads to additional improvements on large-scale test problems. For instance, on the 10k_C500 dataset, the error rate decreases from 0.97% to 0.39%, indicating that the dual-layer structure significantly enhances the model's generalization ability.

Interestingly, the complete method (with both the dual-layer structure and differential evolution) does not always outperform the single-component improvements on small-scale problems. For example, on the 1k_C100 dataset, the error rate of the complete method is 3.58%, slightly higher than the 2.64% achieved by adding only differential evolution. We attribute this to the outer layer's diversity-enhancing strategies, which may introduce additional exploration overhead on small-scale problems where faster convergence is more critical. In contrast, on larger datasets, the collaborative effects of diversity from the outer layer and fast convergence from the inner layer result in superior overall performance.

These results validate the effectiveness of the dual-layer framework and reveal the complementary roles of its components. While the combined approach achieves the most comprehensive improvement overall, the contributions of each component vary depending on the scale and complexity of the problem.

We have included the complete experimental results and analyses in the appendix of the updated manuscript. We hope these additions provide a clearer understanding of the contributions of each component in the dual-layer framework. Thank you again for suggesting the ablation study, which has helped us further analyze the effectiveness of our method. We welcome any further feedback you may have.

We sincerely appreciate your thorough review and thoughtful evaluation of our work. Your recognition of the proposed framework and its experimental results is highly encouraging. At the same time, your constructive comments and insightful questions have provided us with valuable opportunities to improve the clarity, rigor, and overall quality of our manuscript. Below, we address your concerns and provide detailed responses to each of your queries.

W1: The specific contributions of the newly introduced components in the dual-level framework remain unclear.

R1: Thank you for your insightful comment. We acknowledge that the specific roles of each component in our framework and their impacts on the experimental results could be further clarified. To address this, we have redesigned the framework diagram in the manuscript to more intuitively illustrate the structure and workflow of the dual-layer self-evolutionary mechanism: the outer layer optimizes prompt strategies using differential evolution to ensure diversity, while the inner layer generates heuristic strategies guided by the optimized prompts and accelerates the optimization process through differential evolution. The collaboration between these two layers ensures both diversity in the search process and fast convergence.

Specifically, the outer layer initializes a population of prompts and evolves them through crossover and mutation under the guidance of differential evolution. The fitness of each prompt is evaluated, and the best-performing prompts are selected to guide the inner layer. The inner layer, in turn, generates heuristic strategies based on these prompts and further optimizes them with differential memory for directional evolution to refine the search direction. In the revised manuscript, we have added detailed descriptions of the individual modules in both layers and will include additional experimental analyses in the appendix to demonstrate the contributions of these components to the overall performance.

Our new ablation study show that the outer layer effectively prevents the search from stagnating in local optima and enhances generalization to unseen instances, while the inner layer significantly improves convergence speed. The collaborative interaction between the two layers enables efficient solutions for large-scale MILP problems.

We appreciate your suggestion, which has helped us refine the clarity and structure of the manuscript. These revisions have been incorporated into the main text, and we hope the updated version better highlights the design principles of our framework and the specific contributions of its components. We welcome any further feedback you may have.

W2: Additional experimental results are needed to further validate the effectiveness of the proposed method.

R2: Thank you for your valuable suggestion. We have added additional experiments based on the specific suggestions provided in Q1 through Q6 to further validate the effectiveness and superiority of the proposed method. Specifically:

• For Q1, we conducted ablation studies to analyze the roles of the dual-layer structure and the differential evolution mechanism. The experiments demonstrate how the outer layer promotes diversity and the inner layer accelerates convergence, and how their collaborative effects improve the overall performance.
• For Q2, we included results from multiple repeated experiments, which highlight the proposed method's consistency and stability across runs.
• For Q3, we provided concrete examples and analyses of the differential memory mechanism in differential evolution, clarifying how differences in thought and code contribute to strategy optimization.
• For Q4, we analyzed the impact of different population sizes on the experimental results and supplemented experiments with reduced population sizes, showing that our method maintains superiority over baseline methods even with smaller populations.
• For Q5, we compared the performance of our method against EoH in MILP problems, particularly on SC problems, confirming significant improvements over these baselines.
• For Q6, we emphasized the innovative design of the method in balancing convergence and diversity and supplemented experimental results to further highlight this aspect.

Additionally, we plan to include more details and analyses in the appendix of the updated manuscript to demonstrate the generality and robustness of the proposed method across diverse tasks.

We appreciate your suggestions, which have helped us comprehensively improve the experimental validation and methodological analysis.

We provide detailed examples of the evolution process, including the changes in thought and code representations, in Appendix A of the revised manuscript. Additionally, as mentioned in A1 (response to Q1), our ablation experiments further validate the contribution of differential evolution. The results demonstrate that incorporating this mechanism significantly accelerates convergence compared to traditional methods.

We hope these clarifications and examples provide a more comprehensive understanding of the differential evolution mechanism and its role in improving the results. Should you have further questions, we would be happy to address them.

Q4: 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?

A4: Thank you for raising this question. In our experiments, the population sizes for LNS tasks and combinatorial optimization tasks are set differently to ensure fair comparisons with state-of-the-art baselines and to account for the unique characteristics of each problem type.

For combinatorial optimization tasks, such as bin packing (BP) and traveling salesman problem (TSP), we adopted population sizes of 20 and 10, respectively, following the experimental settings in EOH[1]. This alignment ensures fairness in comparisons and consistency with prior work. For MILP problems, we uniformly set the population size to 4, which was determined based on the problem characteristics and computational efficiency considerations specific to large-scale MILP tasks.

To further analyze the impact of population size on experimental outcomes, we conducted additional experiments on the bin packing task, testing our method with a reduced population size of 4. As shown in the table below, although the average performance slightly decreases with a smaller population size, our method still outperforms EOH (population size 20). For example, the average error of our method with a population size of 4 is 1.76%, which is better than EOH’s 2.09%. This demonstrates that our dual-layer framework and differential evolution mechanism exhibit significant robustness and effectiveness, maintaining superior performance even with smaller populations.

Q5: What performance levels do FunSearch and EoH achieve on the LNS tasks? Are their results comparable to those of the proposed method?

A5: Thank you for your question. The proposed method is a framework specifically designed for solving large-scale MILP problems, while FunSearch and EoH are optimization methods focused on discovering strategies for combinatorial optimization problems. Based on existing literature [1], EoH generally outperforms FunSearch on combinatorial optimization tasks. Therefore, we chose to apply EoH in our framework (EoH-LNS) as the primary baseline for comparison with our LLM-LNS method, ensuring representativeness and fairness.

We evaluated both methods on standard combinatorial optimization problems, specifically the SC problem (a minimization task), using instances with 200,000 (SC${}_1$) and 2,000,000 (SC${}_2$) decision variables and constraints. The experimental results indicate that EoH-LNS achieves strong performance on these tasks, but our LLM-LNS method consistently outperforms EoH-LNS across all test instances. For example, on the SC₁ dataset (200,000 variables and constraints), our method improves the average performance by 1.67%, and on the SC₂ dataset (2,000,000 variables and constraints), the improvement reaches 9.20%. These results highlight the superior capability of our method in handling large-scale MILP problems.

The superior performance of LLM-LNS is attributed to its dual-layer self-evolutionary mechanism and differential evolution strategy, which effectively balance diversity and convergence. This allows our method to better address the challenges posed by larger and more complex problem structures.

We also plan to include additional experimental results, including tests applying FunSearch, in the appendix of a forthcoming revised manuscript. This will further validate the advantages of our method in comparison to these baselines. Thank you for your suggestion, which has provided us with valuable direction for further improving our work.

Q2: 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?

A2: Thank you for your thoughtful question. Regarding the number of repeated trials and result consistency, we followed the settings described in the original EoH [1], where a single experiment was conducted for each method, and evaluations were performed across multiple test instances. It is important to clarify that in our proposed method, the seed heuristic strategies are not hand-crafted; instead, they are automatically generated by the large language model (LLM), which introduces some degree of randomness between runs.

To further validate the stability of our method, we conducted additional repeated experiments on the bin packing task. Specifically, we ran three independent trials for both EoH and our method, and the results are summarized in the table below. Despite the randomness introduced by the seed generation, our method consistently outperforms EoH in both effectiveness and stability. For example, on the 1k_C100, 10k_C100, and 10k_C500 test sets, the variance in our results is small, and the average performance is consistently better than EoH. This demonstrates that our dual-layer framework, combined with the differential evolution mechanism, effectively enhances both consistency and generalization.

Q3: 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?

A3: Thank you for your interest in the differential evolution mechanism. Our method leverages prompts to guide the large language model (LLM) in automatically learning the differences between parent strategies, which include both thought and code representations. The core of the differential evolution mechanism in our framework lies in introducing directionality during the traditional crossover process. Specifically, the LLM not only integrates the code and strategies of the parents but also receives feedback on their relative performance (fitness). The prompts explicitly instruct the LLM to learn the transformation path from less effective strategies to more effective ones, enabling guided evolution.

In implementation, the parent strategies prior to differential evolution consist of two components:

1. Thoughts: These are natural language descriptions of the heuristic methods. For example, a parent strategy may describe ranking variables based on their contributions and constraint deviations, or penalizing frequently used edges to optimize a path. After differential evolution, the thought strategies may evolve to include directions such as rewarding infrequent edges to improve diversity or adopting a hybrid strategy combining global search and local optimization. This reflects a directional optimization from local optima toward global optima.
2. Code: The parent strategies are also represented as executable code that implements the current logic. After differential evolution, the updated code may adjust key parameters or introduce new modules to reflect the improved strategy. For instance, it might incorporate random perturbations or dynamically adjust step sizes to enhance robustness.

The key innovation here is that the LLM not only generates new strategies but also understands the improvement directions through differential learning. This approach significantly enhances the effectiveness and convergence speed of the evolutionary process. Compared to traditional crossover without directionality (i.e. merely combining parent strategies), our differential evolution mechanism is far more targeted and efficient.

Q6: 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?

A6: Thank you for this thought-provoking question. The application of LLM-designed heuristics in LNS for MILP has provided new insights, particularly in balancing convergence and diversity to achieve high-performance search algorithms. Our proposed dual-layer self-evolutionary framework effectively combines strategies for optimizing both convergence and diversity, addressing the core challenges of large-scale optimization tasks. Specifically:

In optimization tasks, convergence ensures that the algorithm quickly finds high-quality solutions, while diversity prevents the algorithm from getting trapped in local optima and enables the exploration of better solutions. Our framework achieves this balance through a dual-layer design: the outer layer uses differential evolution to optimize prompts, focusing on enhancing the diversity of search strategies, while the inner layer applies differential evolution to rapidly optimize heuristic strategies, thereby accelerating convergence. The collaboration between these two layers enables the framework to deliver superior performance across problems of varying scales.

Our experimental results validate this balance. As demonstrated in the ablation study discussed in the response to Q1, incorporating the differential evolution mechanism alone significantly improves convergence in small-scale problems, such as reducing the error on the 1k_C100 dataset from 4.48% to 2.64%. Building on this, the addition of the dual-layer structure further improves generalization on large-scale problems, reducing the error on the 10k_C500 dataset from 0.97% to 0.39%. This balance between convergence and diversity allows our framework to excel in LNS applications for MILP.

From a methodological perspective, the LLM-driven heuristic approach not only automates the discovery of improvement directions in strategies but also captures the evolutionary pathways of strategies through a differential memory mechanism. This automation enhances the generality and adaptability of the framework, presenting a novel approach to solving large-scale MILP problems. The use of LLMs to design and optimize heuristics represents a significant shift toward leveraging pre-trained models for automated strategy generation, reducing reliance on hand-crafted heuristics and domain-specific expertise.

We will provide additional experimental results and detailed analyses in the updated manuscript to further illustrate how these insights contribute to advancing the performance of search algorithms. Thank you again for raising this question, which has allowed us to more comprehensively highlight the innovations and experimental implications of our method.

References

[1] Liu F, Xialiang T, Yuan M, et al. Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model[C]. Forty-first International Conference on Machine Learning. 2024.