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

We sincerely thank Reviewer 4X7L for the thoughtful and constructive feedback. We are glad that you find the proposed LLM-LNS framework innovative and recognize its performance improvements over existing methods. We appreciate your suggestions regarding dataset realism, solver settings, and related work, and we address each of these points in detail below.

Claims And Evidence and Weakness:

A1: Thank you very much for the helpful suggestion. We fully agree that evaluating on realistic datasets is important. While MIPLIB 2017 is a valuable benchmark, many of its instances are either heterogeneous or not large enough to meaningfully evaluate LLM-driven heuristics. Therefore, we carefully selected two problem classes from MIPLIB — dws and ivu — which both contain multiple large-scale instances of the same type, allowing for a meaningful train/test split and consistent evaluation.

Specifically, we used the largest instances from each class as the test set, and the remaining instances for training. All methods were evaluated under a 3000s time limit. The results below demonstrate that LLM-LNS generalizes well to realistic, large-scale industrial problems. We will include these experiments in the appendix and plan to evaluate broader MIPLIB categories in future work.

Experimental Designs Or Analyses:

A1: Thank you for the question. We used the default settings for both Gurobi and SCIP. To ensure a fair comparison, all baselines were run under the same computational constraint: 16 cores and 32 threads within a fixed time limit. We will include a description of these settings in the Experimental Setup section of the revised manuscript.

Supplementary Material:

A1: Thank you very much for the suggestion! We agree that moving Algorithm 1 into the main text would help clarify the overall workflow of our method. We will include it in the main paper if space permits during the revision.

Essential References Not Discussed:

A1: Thank you very much for pointing this out. BTBS-LNS is a recently accepted paper at ICLR 2025, which proposes a reinforcement learning-based LNS framework with a binarized-tightening and branching mechanism for solving MIP problems. While the approach is related in spirit, the code is not publicly available at this time. Moreover, the experiments in BTBS-LNS are mainly conducted on relatively small-scale problems (typically with tens of thousands of decision variables), and our previous experience suggests that reinforcement learning struggles to scale effectively in much larger problem settings, which are the main focus of our work. We will add a discussion of BTBS-LNS in the Related Work section, and if the code is released in time, we will consider including a comparative experiment in the final version.

We sincerely appreciate Reviewer 4X7L’s insightful comments and constructive suggestions. They have helped us significantly improve the clarity and completeness of our paper. We have carefully addressed each point in our revision and will incorporate the proposed changes into the final version. Thank you again for your thoughtful review and valuable feedback.

We sincerely thank Reviewer r212 for the detailed, thoughtful, and constructive feedback. We greatly appreciate your recognition of the contributions and your suggestions for improving the clarity, robustness, and completeness of the work.

Methods And Evaluation Criteria:

A1: We agree that fully evaluating high-level LLM behavior is challenging. As suggested, we will include the full evolution traces of both strategies and prompts in the appendix to improve interpretability. Regarding instance realism, as noted in our response to Reviewer 4X7L, we have added experiments on two large-scale MIPLIB problem classes to further validate the robustness of our method.

A2: CL-LNS was designed for small-scale MILPs and struggles to scale to our large instances with hundreds of thousands of variables. Training takes over 8 hours per instance, and inference is 30× slower than our method, making it impractical. Following your suggestion, we added CP-SAT (16 threads, both original and use_lns_only) as a new baseline. As shown in Table 1 at the supplementary link, CP-SAT supports only integer programs and performs well on easier problems like MIS and MVC. However, on more complex large-scale tasks such as SC${}_{2}$, its performance lags behind several other baselines. Our method still outperforms all baselines across tasks. Due to time constraints, further analysis of CP-SAT—including using it as a subsolver to enhance LLM-LNS—will be included in future work.

Experimental Designs Or Analyses:

A1: We agree your suggestions help better highlight our method’s strengths. We will revise the paper to include Figure 8 in the main text if space permits. Following your advice, we also report the primal integral in Supplementary Table 2, which further confirms the effectiveness of LLM-LNS. We appreciate your point on the deployment advantage of LLM-based methods and will add a note on this practical benefit in the revision.

A2: Our method evolves prompt strategies during training, not inference, so it does not affect solving efficiency. Although we add a prompt evolution layer, its total time remains comparable to EOH, with minor overhead from fitness evaluation via testing. Evolution times (in minutes) for BinPacking and TSP over 20 generations are reported in Rebuttal to Reviewer G8Pp, and will be added to the appendix.

A3: You're absolutely right—setting a time limit per subproblem is important for robustness. In our implementation, we do impose a maximum time per LNS iteration: 100 seconds for problems with ~100K variables, and 200 seconds for ~1M variables. We will clarify this in the experimental setup section of the paper.

A4: We agree that unnormalized averaging may be biased on heterogeneous datasets. In ongoing work, we explore multi-metric fitness (e.g., gap estimation integral, k-step improvement rate). We will briefly discuss this in the Appendix as a direction for future work.

A5: The terms site, value, and constraint describe the constraint matrix: involved variables, coefficients, and RHS. We'll clarify this in the paper. In ongoing work, we observe that giving full constraint details may lead to strategies with high time complexity. We're exploring feature extraction to simplify inputs, and will discuss this in the Appendix.

Other Comments Or Suggestions:

A1&A3: We have updated the plots to report the best-so-far solution at each time step. The corrected results are shown in Appendix Figures 1–4. The primal integral results (based on the best-so-far solutions) have been added in Appendix Table 2.

A2: We have added the minimization or maximization indicator for each problem in Appendix Table 1. If helpful, we can further include a primal gap comparison in the Appendix to make the results clearer.

A4&5&8&9: We agree this will make the paper clearer, and will revise the corresponding sections.

A6: We confirm that, following the same setup as EOH and FunSearch, we use five TSPLib instances (d198, eil76, rat99, rl1889, and u1060) as the training set for evolving our policies. None of the other TSPLib instances used in evaluation are seen during training. We will update Table 17 to clearly mark this.

A7: We have explained the difference between set 1 and set 2 in Appendix Table 5 (Sec. C.5). We'll also add a sentence in the main text to clarify this and point to the appendix.

A10: We will revise Appendix C.5 to include a clear description of the instance generation process.

A11: We will include the final heuristics in the code and highlight key algorithmic directions in the appendix to aid interpretability and better understand LLM behavior.

Due to the rebuttal length limit, supplementary figures and tables are provided at https://anonymous.4open.science/r/Supplementary-Figures-and-Tables-8DBB/. If any part of our response is unclear or insufficient, we would be very happy to further clarify and continue the discussion.

We sincerely thank Reviewer fpWD for the positive and encouraging feedback. We are glad that you found our method interesting and the experimental design sound. Your recognition of the contributions and the clarity of our work is truly appreciated and motivates us to further refine and extend our research.

We sincerely thank Reviewer G8Pp for the thorough review and positive evaluation of our work. Your encouraging comments and constructive suggestions are highly appreciated and have helped us further improve the clarity and completeness of the paper.

In the following, we address your concerns and questions point by point.

Strengths And Weaknesses:

A1: Thank you for this valuable comment. We would like to clarify that the instances used in our experiments are not arbitrarily selected, but are generated based on standard formulations of canonical MILP problems, as described in Appendix C.5. For each problem class and size range, instances are randomly sampled from the same distribution. Training and testing sets are formed via random partitioning, which ensures fair evaluation and avoids selection bias. We will make this clearer in the main text and explicitly refer readers to Appendix C.5, where we have also added pseudocode for the instance generation process.

A2: Thank you very much for your suggestion! We agree that ReEvo [1] is an important baseline. As detailed in Appendix H.7, we conducted a comparative experiment on the Bin Packing problem under the same settings. When using lightweight models such as GPT-4o-mini, our method exhibited significantly better stability and achieved superior performance across all test instances. We plan to add a summary of this comparison in the main text and include a pointer to Appendix H.7 for clarity.

A3: Thank you for your insightful comment. While our differential memory mechanism shares conceptual similarities with the reflection-based evolution in ReEvo, there are key differences in both design and learning strategy. ReEvo employs a pairwise comparison of parent strategies based on short-term memory. In contrast, our approach learns from differences across multiple parents, enabling the discovery of more directional and effective evolutionary strategies. By leveraging the objective values of these strategies, the large language model performs contrastive learning to internalize beneficial search directions. Furthermore, differential memory is integrated into a dual-layer agent architecture, allowing deeper interaction between prompt optimization and strategy generation. We will clarify these differences in Appendix H.7.

Questions For Authors:

A1: Thank you for the question. Our method adopts a dual-layer self-evolutionary agent, where the outer layer evolves prompt strategies and the inner layer evolves heuristic strategies. In the outer layer, prompt strategies guide the LLM to generate new heuristics through fixed crossover and mutation templates. While these operators are fixed, the prompt strategies themselves evolve dynamically: they are evaluated based on the performance of the heuristics they produce, and low-performing prompts are pruned over time. This design enables adaptive exploration while maintaining diversity and preventing premature convergence.

A2: Thank you for the question. Our method follows a learning-based optimization paradigm, where evolution takes place during the training stage, not inference. Therefore, it does not affect solving efficiency.

Although we introduce an additional layer for prompt strategy evolution, the overall evolution time remains comparable to EOH. The slight overhead mainly comes from evaluating new prompt strategies through testing, which is necessary to compute their fitness.

To provide a concrete comparison, the total evolution time on the 20th generation is:

• BinPacking: Ours – 144.7 minutes, EOH – 138.7 minutes
• TSP: Ours – 67.3 minutes, EOH – 59.6 minutes

We believe this small difference is acceptable given the improved performance, and again, it occurs only during training, not during actual problem solving.We will include these results in the appendix to provide a more detailed comparison. Thank you again for the helpful suggestion.

Thank you again to Reviewer G8Pp for the valuable suggestions — they will undoubtedly help us improve the paper.