LLM4Solver: Large Language Model for Efficient Algorithm Design of Combinatorial Optimization Solver

W1: The novelty of the manuscript is limited. There are several existing LLM-based heuristic generation methods [1-3] that employ Initialization, Crossover, and Mutation promptings to generate heuristics. The only innovation of the proposed method seems to incorporate the multi-objective fitness function.

W2: The description of the method is vague and the use of mathematical symbols is repetitive. For example, on Page 4, $n$ denotes the number of objectives. In Eq. (2), $n = 1, 2, ...,N$. In addition, in Eq. (1), $N_{ins}$ denotes the number of instances used for fitness evaluation. In Algorithm 2, $M$ denotes the number of instances. On Page 16, $r=1$. In Algorithm 2, $k = 1, 2, … ,r$.

W3: In Section 4, my primary concern is the lack of comparison with other SOTA LLM-based heuristic generation methods, such as [1-3]. Given that the limited innovation of LLM4Solver lies in the multi-objective fitness function, I am hesitant to assume that the proposed LLM4Solver would outperform EoH [2] and ReEvo [3] on single-objective problems.

W4: In the ablation study, the authors assess the effectiveness of components such as crossover and mutation. As I mentioned in W1, the prior studies [1-3] have demonstrated the effectiveness of these components. The authors should instead focus on evaluating the effectiveness of their multi-objective fitness function, which is the main contribution of this manuscript.

W5: As far as I know, generating heuristics with an LLM requires a predefined seed function; however, this manuscript, including its appendix, lacks any mention of such a seed function. The authors should clarify how the seed function is predefined.

W6: Several concepts are not adequately defined, and there are numerous grammatical errors. For instance, the values in brackets in Table 1 are not explained. On Page 3, the phrase "After generations of iteration" is unclear. On Page 6, the sentence "Specifically, we employ elitism survivor selection (Zhou et al., 2019), which always selects the N individuals with the best fitness from the total (r + 1)N ones after crossover and mutation" has grammatical errors. Additionally, on Page 17, this manuscript mistakenly refers to "gpt35" instead of "gpt3.5."

[1] Mathematical discoveries from program search with large language models. Nature, 625:468–475, 2024.

[2] Evolution of heuristics: Towards efficient automatic algorithm design using large language model. In International Conference on Machine Learning, 2024.

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

• I find the title too broad and does not reflect the scope of this work. I prefer the author adds phrases along the line of “LLMs for diving heuristic” in their title, as this work only considers designing diving heuristics but not other components of MILP solvers.
• I find contribution of the paper a bit weak, as the algorithm pipeline mainly builds on top of [1].
• Limited learning baselines have been compared in the paper. The number of MIPLIB instances evaluated (20) is too small.

[1] Liu, Fei, et al. "Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model." Forty-first International Conference on Machine Learning. 2024.

1. Methodological Innovation: The core methodological contribution of the paper appears to closely resemble the Evolution of Heuristics (EOH) approach[1], with the main difference being its application to diving heuristics. The paper does not clearly differentiate itself from EOH. A more explicit discussion of the differences, as well as a comparison with EOH in the experiments, would strengthen the contribution.
2. Lack of Comprehensive Solver Comparison: The title and abstract emphasize the role of LLMs in enhancing combinatorial optimization solvers, yet the experiments only compare LLM4Solver against SCIP, which is known to be weaker than state-of-the-art solvers like Gurobi and CPLEX. A broader comparison with these solvers is necessary to validate the general claim of improving CO solvers.
3. Small Problem Instances: The experiments are conducted on relatively small problem instances, which limits the scope of the evaluation. In some literatures[2][3], approaches have been tested on large-scale mixed-integer linear programming (MILP) problems with millions of variables and constraints. It would be valuable to see how LLM4Solver performs on larger-scale problems to understand its scalability and broader applicability.
4. Comparison with Learn2Branch: There are many ways to enhance CO solvers, and Learn2Branch[4][5][6] is a significant direction in this field. The paper uses Learn2Dive, but it does not clearly explain the advantages of Learn2Dive over Learn2Branch, which is a well-established method in CO solver research. A comparison with mainstream Learn2Branch methods would help demonstrate the effectiveness of the proposed approach in enhancing solver performance.
5. Application to Other CO Solvers: The paper focuses on improving the SCIP solver's diving heuristic, but it would be interesting to see how the LLM4Solver framework can be applied to other solvers, especially domain-specific ones like Concorde for the traveling salesman problem (TSP). This could provide insights into the general applicability of the proposed method across different types of CO solvers.

[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.

[2] Deb K, Pal K. Efficiently solving: A large-scale integer linear program using a customized genetic algorithm[C]//Genetic and Evolutionary Computation–GECCO 2004: Genetic and Evolutionary Computation Conference, Seattle, WA, USA, June 26-30, 2004. Proceedings, Part I. Springer Berlin Heidelberg, 2004: 1054-1065.

[3] 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.

[4] Gasse M, Chételat D, Ferroni N, et al. Exact Combinatorial Optimization with Graph Convolutional Neural Networks Supplementary Materials[J].

[5] Gupta P, Gasse M, Khalil E, et al. Hybrid models for learning to branch[J]. Advances in neural information processing systems, 2020, 33: 18087-18097.

[6] Gupta P, Khalil E B, Chetélat D, et al. Lookback for learning to branch[J]. arXiv preprint arXiv:2206.14987, 2022.

1. While several LLM-based optimization works have emerged in recent years, I’ve listed a few key papers below [1]-[6]. The current paper primarily compares its approach to the work of Kuang et al. in both the motivation and experimental sections. However, the idea of using LLMs to prompt code for optimization does not seem particularly novel. The authors should expand their comparisons to include these additional works, both theoretically and experimentally.

2. Additionally, there are various methods that focus on the symbolic discovery of new operators (without using LLMs). It would be beneficial for the authors to compare their approach with these methods to discuss the advantages and disadvantages of leveraging large models in this context.

3. Regarding the initialization, crossover, and mutation steps, what clear advantages does the LLM offer over traditional random code block operations? Can you provide specific empirical data or examples to support this claim? This would help in better justifying the proposed method.

4. The sensitivity of the method to the prompt is a key concern, but this aspect is not thoroughly investigated in the paper. I recommend that the authors explore this issue more deeply.

5. It would also be helpful to provide a clearer description or example of how the code evolves throughout the iterations of the genetic evolution process. A step-by-step demonstration would make it easier for readers to understand the role of the LLM in the evolution of the code.

6. The experimental comparison appears limited. The seven human-designed heuristics used in the experiments are relatively simple, and the proposed method is only compared against L2DIVE. Given the rapid development of this field, it is difficult to assess whether the proposed method is truly SOTA. Furthermore, I am curious about how the method performs in comparison to evolutionary methods and neural combinatorial methods. While it may not be necessary to outperform all existing methods, a more comprehensive comparison would provide better insight into the performance of the proposed approach.

7. The overall method design seems relatively straightforward and appears to rely heavily on the capabilities of LLMs. Many of the observed performance enhancements seem to stem from the LLM’s abilities rather than the intrinsic design of the algorithm itself. A clearer discussion of the algorithm's design and its novelty would be beneficial. Additionally, do the strong reasoning capabilities of models like OpenAI's o1-preview and o1-mini provide additional advantages for LLM4Solver?

8. The section on multi-objective evolution for cross-benchmark generalization needs further clarification. How does multi-objective evolution contribute to cross-benchmark generalization? Additionally, the experiments conducted to verify this claim should be explained in greater detail.

[1] Evolution of heuristics: Towards efficient automatic algorithm design using large language model

[2] LLaMoCo: Instruction tuning of large language models for optimization code generation

[3] LLaMEA: A large language model evolutionary algorithm for automatically generating metaheuristics

[4] ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution

[5] Autonomous multi-objective optimization using large language model

[6] OptiMUS: Optimization Modeling Using MIP Solvers and large language models

1. As this paper is also an evolutionary algorithm-based method, it doesn't have a comparison to previous related papers like EoH by Liu et al. (2024) and ReEvo by Ye et al. (2024).
2. Limited novelty as the main ideas of LLM4Solver has implemented in previous works for solving COP.