Efficient Heuristics Generation for Solving Combinatorial Optimization Problems Using Large Language Models

Authors: Xuan Wu, Di Wang, Zhiguang Cao, Chunguo Wu, Lijie Wen, Chunyan Miao, Yubin Xiao, You Zhou
Primary area: generative models
Keywords: Heuristic Generation, Large Language Models, Combinatorial Optimization Problem

Abstract:
Recent studies exploited Large Language Models (LLMs) to autonomously generate heuristics for solving Combinatorial Optimization Problems (COPs), by prompting LLMs to first provide search directions and then derive heuristics accordingly. However, the absence of task-specific knowledge in prompts often leads LLMs to provide unspecific search directions, obstructing the derivation of well-performing heuristics. Moreover, evaluating the derived heuristics remains resource-intensive, especially for those semantically equivalent ones, often requiring unnecessary resource expenditure. To enable LLMs to provide specific search directions, we propose the Hercules algorithm, which leverages our designed Core Abstraction Prompting (CAP) method to abstract the core components from elite heuristics and incorporate them as prior knowledge in prompts. We theoretically prove the effectiveness of CAP in reducing unspecificity and provide empirical results in this work. To reduce the required computing resources for evaluating the derived heuristics, we propose few-shot Performance Prediction Prompting (PPP), a first-of-its-kind method for the Heuristic Generation (HG) task. PPP leverages LLMs to predict the fitness values of newly derived heuristics by analyzing their semantic similarity to previously evaluated ones. We further develop two tailored mechanisms for PPP to enhance predictive accuracy and determine unreliable predictions, respectively. The use of PPP makes Hercules more resource-efficient and we name this variant Hercules-P. Extensive experiments across various HG tasks, COPs, and LLMs demonstrate that Hercules outperforms the state-of-the-art LLM-based HG algorithms, while Hercules-P excels at minimizing computing resources. In addition, we illustrate the effectiveness of CAP, PPP, and the other proposed mechanisms by conducting relevant ablation studies.

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

Reviews and discussion:
<thread>
creation date:
1730102082668

thread_type:
official_review

<thread_object>
creator: reviewer_f4hd

<content>
summary:
This paper explores the application of LLM in autonomously generating heuristics to solve COPs and proposes a novel algorithm named Hercules to address the two main challenges of existing approaches.

Hercules utilizes the Core Abstraction Prompting (CAP) method to abstract core components from elite heuristics and incorporate them as prior knowledge in prompts, thereby reducing the specificity of search directions. This paper further introduces Hercules-P, an efficient variant of Hercules that integrates CAP with the novel Performance Prediction Prompting (PPP) method. PPP leverages LLMs to predict the fitness values of newly derived heuristics based on their semantic similarity to previously evaluated ones, significantly reducing the required computing resources.

strengths:
1. The paper is laudable for its well-structured and logical presentation, providing a comprehensive understanding of the research topic.

2. The article is praiseworthy for its extensive experimental data and significant findings. The authors have selected a number of baselines for comparative experiments on different benchmarks.

3. The supplement provided in this article is adequate. It explains in detail for the reader what is not expanded in detail in the paper, including specific experimental data, hyperparameter settings, Critical Difference Analysis, etc.

weaknesses:
1. In the literature of TSP and CVRP, it is known that those conventional heuristic algorithms, such as LKH [1] and EAX [2], exhibit robust performance. It appears, however, that this submission does not address LKH and EAX, nor does it provide a comparative analysis of the proposed algorithm against these established methods.

1. In lines 85-100 of the Introduction section, the authors describe two challenges to LLM-based HG methods, mentioning in the second challenge that these methods introduce numerous linear operations and conditional branches that make the GPU less efficient for these algorithms. In lines 113-128, the authors claim to have proposed Hercules-P in order to better address the second challenge, but I don't seem to have read in the manuscript how Hercules-P reduces linear operations and conditional branches, making GPUs more efficient in processing these algorithms. May I ask if the authors have solved this challenge? If not, these representations are inappropriate.

2. Does the appearance of CVRP in Section 4.4 stand for Capacitated Vehicle Routing Problem? The authors do not explain what CVRP stands for in the body of the manuscript, and the only explanation appears in the code comments in the Appendix section (line 1337). This cannot be very clear to the reader when it comes to understanding the manuscript.

3. In Section 2.3, the authors mention two challenges for NCO solvers: improving generalisation capabilities and large-scale COPs performance. In Table 5, for LEHD, the performance improvement of either Hercules or Hercules-p gradually decreases as the problem size of TSP or VCRP increases. Does this mean that Hercules also fails to address the challenges faced by NCO solvers? Can Hercules still provide performance gains when the problem size is larger? Further discussion is requested from the authors.


## References
[1] Keld Helsgaun. General k-opt submoves for the Lin-Kernighan TSP heuristic. Mathematical Programming Computation 1(2-3): 119-163 (2009)

[2] Yuichi Nagata, Shigenobu Kobayashi. A Powerful Genetic Algorithm Using Edge Assembly Crossover for the Traveling Salesman Problem. INFORMS Journal on Computing 25(2): 346-363 (2013)

questions:
Please reply to my comments in "Weaknesses".
</content>
</thread_object>

</thread>
<thread>
creation date:
1730484503148

thread_type:
official_review

<thread_object>
creator: reviewer_qjjz

<content>
summary:
The paper proposes a framework to use LLMs to generate heuristics for solving
optimization problems. The authors describe their framework and evaluate it
empirically, comparing to other approaches in the literature.

strengths:
The proposed framework is interesting and seems to work well in practice.

weaknesses:
The choice of KGLS as seed heuristics should be justified as it was not designed
for the general TSP. Why not LKH? This should also be considered in the
empirical evaluation; in particular to answer the question of whether KGLS is a
reasonable heuristic to start with in this case (improving over a weak heuristic
is easier than improving over a strong heuristic).

Figure 5 has no axis labels.

questions:
The differences are small in some cases and it would be great if the authors could
provide error bounds or confidence intervals for the empirical results.

Why is KGLS is reasonable base heuristic?

Update after responses: Thank you for your responses. I have updated my score.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730680576517

thread_type:
official_review

<thread_object>
creator: reviewer_kgdn

<content>
summary:
This paper studies the generation of heuristics for combinatorial optimization problems using LLMs. 

The work continues similar work in this space that tries to mimic evolutionary computation (crossover, mutation) via LLMs. The result is an LLM-infused metaheuristic algorithm. 

Unlike the previous work, the paper claims 1) to address introducing more problem specificity into the prompts and 2) to speed up the process by using LLMs to predict the performance of generated accuracies to skip over evaluating them fully. 

Overall, I enjoyed reading this paper, and I appreciated the work that went into building an end-to-end pipeline with several components.

strengths:
Integrating LLMs with heuristic solving is an exciting combination. 
The paper implements an end-to-end pipeline that starts with a seed query that then mimics evolutionary computing via LLMs, yielding heuristics that can be embedded in the Local Search Meta-Heuristics for different combinatorial problems. 
The connection with Information Gain is an excellent addition
From a practical perspective, the paper considers several details into account such as reducing costs via LLM predictors.

weaknesses:
As rightly noted in the paper, the idea of mimicking evolutionary computation via LLMs is not new. In fact, most (all?) crossover and mutation operators are from Ye et. al. 2024. On the one hand, the experiments and the ablation study show that the proposed modifications might offer some benefit in the results, and on the other hand, they can be regarded as incremental, and it is not clear what's the main takeaway. 

Regarding the presentation, I found it difficult/confusing that many moving parts are introduced as large components with several acronyms Hercules, CAP, PPP, EXEMPLAR, Cons --but after all, the provided pseudocode shows the overall algorithm, so I am not sure what these abstractions add to the presentation. Also, the paper claims our "propriety" CAP algorithm  --what does that mean? 

The idea of adding more specificity to the prompts seems reasonable at a high level, but the paper overindexes too much into the example in Figure 1. The information gain analysis is interesting (and is borrowed from a Hu et. al. 2024) but at the end what happens is we select top-k core components. And that's also not uniform, we do that only some number of iterations (denoted by \lambda in the paper), all of which remain as more hyper-parameters to deal with.

The experiments cover TSP, CVPR, Binpacking, Multi-Knapsacks. Importantly, the starting seed function seems critical to the approach. The method generates heuristics but the overall approach to solve these problems are meta-heuristics.  (please correct me if I understand this correctly). For TSP, we use guided local search. For BinPacking and Knapsacks we use Ant-Colony Optimization. One might argue that the settings of the outer meta-heuristics and their performance are crucial to the overall results and not just the heuristics (generated by LLMs here.) The experiments do not discuss or study any of this. 

Additionally, all comparisons are with other LLM-based heuristics generations. Note that this is quite a costly approach (hence some effort with performance predictors to save time etc.). According to the tables in the appendix, we are consuming many many minutes upto 5 hours. Then, it is not clear to me how to fairly evaluate these results. How does the same GLS and ACO without the advanced heuristics found by LLM but with standard heuristics perform given the same amount of time? (Btw, does this time include LLM queries or only running the heuristics after the LLM generates them against the instances?) 

This might not be surprising that the choice of LLM quite affects the results (Table 1; LLama vs GPT-4o). But then it makes one wonder how much of the value comes from the many moving components proposed here vs. plain and simple, the underlying LLM.

questions:
Could you provide details on the outer meta-heuristics (GLS, ACO etc.)? How much of the results are due to the LLM integration with CAP, PPP etc. vs. the meta-heuristics leading the search into good solutions. 
It would be interesting to know the comparison between default GLS, ACO or even other baselines for TSP, BinPacking, MKP to position the results in this paper. As is, it is hard to evaluate the significance
</content>
</thread_object>

</thread>
<thread>
creation date:
1730685424040

thread_type:
official_review

<thread_object>
creator: reviewer_jj2y

<content>
summary:
The paper presents Hercules, an LLM-based algorithm for generating heuristics for combinatorial problems. The paper seems to extend the framework in Ye et al., 2024 with a more advanced direction generation (based on identifying core components in heuristics) as well as an LLM-based fitness calculation. The experiments show gains over the baselines.

strengths:
Strengths:
- The topic is interesting and of recent interest
- The approach (CAP and PPP) seems novel.
- The experiments show significant gains over the baselines in deriving penalty heuristics for guided local search, as well as more moderate gains on constructive heuristics for TSP, heuristic measures for ant colony optimization, and reshaping of attention scores in neural combinatorial optimization,

weaknesses:
Weaknesses:
- I found the claim about information gain to be quite confusing. 
	- First, a lot of information is missing: why the number of core components corresponds to the number of heuristics (can we not have multiple core components per heuristic or the same core component in multiple heuristics)? why do we assume that the set of all possible directions can be partitioned into mutually exclusive subsets that correspond to components (can we not have the same direction for multiple core components)?
	- Second, it is really not clear why the information gain means we get better heuristics (as indicated in lines 284-285)? If the components generated are of low-quality the directions may be of lower quality as well.

- Experimental evaluation:
	- It is not clear what is being reported under gain: the definition is based on "the performance of ..." but it is not clear how performance is measured.

- Writing: the writing could improve as a lot of information is not clearly presented. For example there are no clear definitions for a range of terms like parent heuristics, elite heuristics, etc.

- The paper does not provide significant insight into the impact of the proposed techniques (CAP and PPP) beyond the experimental results. For example, it would be interesting to show an analysis of the correlation between predicted fitness values and quality of heuristics.

questions:
I would appreciate the authors response and clarification on the points listed under "weaknesses"
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper presents prompt and other refinements operating on the top of an LLM to guide a meta-heuristic approach dedicated to combinatorial optimization.
The approach continues the work done by Fei Liu et al, 2024 (ICML) and Haoran Ye et al, 2024 (NeurIPS). 
The improvements come from the proposed core abstraction prompting (CAP) and the performance prediction prompting (PPP). Reminiscent of NAS, the authors also provide a generation of heuristics samples (EXAMPLAR) and a confidence stratification module (ConS) enhancing PPP.