LLM-Driven Instance-Specific Heuristic Generation and Selection

Shaofeng Zhang, Shengcai Liu, Ning Lu, Jiahao Wu, Ji Liu, Yew-Soon Ong, Ke Tang

Abstract

Combinatorial optimization problems are widely encountered in real-world applications. Designing high-quality heuristic algorithms that efficiently approximate optimal solutions within reasonable time is a critical research challenge. In recent years, many works have explored integrating Large Language Models (LLMs) with Evolutionary Algorithms to automate heuristic algorithm design through prompt engineering. However, these approaches generally adopt a problem-specific paradigm, applying a single algorithm across all problem instances, failing to account for the heterogeneity across instances. In this paper, we propose InstSpecHH, a novel framework that introduces the concept of instance-specific heuristic generation. InstSpecHH partitions the overall problem class into sub-classes based on instance features and performs differentiated, automated heuristic design for each problem subclass. By tailoring heuristics to the unique features of different sub-classes, InstSpecHH achieves better performance at the problem class level while avoiding redundant heuristic generation for similar instances, thus reducing computational overhead. This approach effectively balances the trade-off between the cost of automatic heuristic design and the quality of the obtained solutions. To evaluate the performance of InstSpecHH, we conduct experiments on 4,500 subclasses of the Online Bin Packing Problem (OBPP) and 365 subclasses of the Capacitated Vehicle Routing Problem (CVRP). Experimental results show that InstSpecHH demonstrates strong intra-subclass and inter-subclass generalization capabilities. Compared to previous problem-specific methods, InstSpecHH reduces the average optimality gap by more than 5.6% for OBPP and 0.9% for CVRP. These results highlight the potential of instance-aware automatic heuristic design to further enhance solution quality.

Introduction

Combinatorial Optimization (CO) problems, such as the Online Bin Packing Problem (OBPP) and the Capacitated Vehicle Routing Problem (CVRP), are fundamental to logistics and scheduling but are notoriously NP-hard. Finding optimal solutions is often computationally prohibitive, leading researchers to rely on heuristics—efficient "rules of thumb" that provide high-quality approximations.

Recent advancements have leveraged Large Language Models (LLMs) paired with Evolutionary Algorithms (EAs) to automate the design of these heuristics. Frameworks like Evolution of Heuristics (EoH) and ReEvo have shown promise by using LLMs to iteratively refine algorithm code. However, these methods typically follow a "problem-specific" paradigm, generating a single heuristic for an entire problem class. This approach ignores instance heterogeneity: a heuristic optimized for one set of parameters (e.g., small items in bin packing) may perform poorly on another (e.g., large items). InstSpecHH addresses this by shifting to an "instance-specific" paradigm.

Methodology

The InstSpecHH framework consists of three integrated stages designed to move beyond "one-size-fits-all" solutions.

The InstSpecHH framework overview, illustrating the three main stages: representation, design, and selection.

1. Problem Instance Representation

Rather than treating a problem class as a monolith, InstSpecHH partitions it into subclasses based on key features. LLMs are utilized to identify relevant feature dimensions and generate natural language descriptions for each subclass. For example, in OBPP, features might include item count, weight distribution, and arrival sequence.

Examples of natural language descriptions generated for problem subclasses in OBPP and CVRP.

2. Heuristic Algorithm Design

For each identified subclass, an LLM-driven evolutionary process is initiated. The LLM acts as a mutation and crossover operator, generating Python code for heuristics. These candidates are evaluated against instances within the specific subclass, and performance feedback is used to guide the next generation of code. To prevent stagnation, a Neighbor Search (NS) mechanism is employed, where heuristics developed for similar subclasses are tested on the target subclass, facilitating the transfer of effective strategies.

3. Heuristic Algorithm Selection

When a new instance is encountered, the system calculates its distance to existing subclasses. It identifies the top-$k$ most relevant heuristics and uses an LLM to select the most appropriate one. This selection is based on semantic reasoning, where the LLM compares the instance's specific features against the descriptions of the candidate heuristics.

Experimental Evaluation

The framework was rigorously tested on two benchmarks:

  • Online Bin Packing Problem (OBPP): 4,500 subclasses defined by item count, distribution (Uniform, Gaussian, Weibull), and capacity ratios.
  • Capacitated Vehicle Routing Problem (CVRP): 365 subclasses defined by customer locations, demand distributions, and vehicle capacities.

The evaluation focused on both intra-subclass generalization (performance on new instances from known subclasses) and inter-subclass generalization (performance on entirely unseen subclasses).

Results and Discussion

InstSpecHH demonstrated significant improvements over state-of-the-art (SOTA) problem-specific methods. In intra-subclass tests, it achieved a near-zero optimality gap. More importantly, in inter-subclass generalization tests, it reduced the average optimality gap by 5.67% for OBPP and 0.95% for CVRP compared to single-heuristic methods like EoH.

A key insight from the study is the dual role of the LLM. While its ability to generate code is well-documented, its performance as a strategic selector is equally vital. Semantic reasoning allows the LLM to match problem characteristics to algorithmic strengths more effectively than simple distance-based metrics. Furthermore, the Neighbor Search mechanism proved essential for escaping local optima by "cross-pollinating" ideas across the subclass space.

Conclusion

InstSpecHH represents a significant step toward instance-aware automated algorithm design. By balancing the computational cost of generation with the performance gains of specialization, it provides a scalable framework for complex CO problems. Future work will focus on reducing the offline computational overhead through more efficient models and pruning redundant heuristics from the generated library to streamline the selection process.

Summary updated

Abstract

Combinatorial optimization problems are widely encountered in real-world applications. Designing high-quality heuristic algorithms that efficiently approximate optimal solutions within reasonable time is a critical research challenge. In recent years, many works have explored integrating Large Language Models (LLMs) with Evolutionary Algorithms to automate heuristic algorithm design through prompt engineering. However, these approaches generally adopt a problem-specific paradigm, applying a single algorithm across all problem instances, failing to account for the heterogeneity across instances. In this paper, we propose InstSpecHH, a novel framework that introduces the concept of instance-specific heuristic generation. InstSpecHH partitions the overall problem class into sub-classes based on instance features and performs differentiated, automated heuristic design for each problem subclass. By tailoring heuristics to the unique features of different sub-classes, InstSpecHH achieves better performance at the problem class level while avoiding redundant heuristic generation for similar instances, thus reducing computational overhead. This approach effectively balances the trade-off between the cost of automatic heuristic design and the quality of the obtained solutions. To evaluate the performance of InstSpecHH, we conduct experiments on 4,500 subclasses of the Online Bin Packing Problem (OBPP) and 365 subclasses of the Capacitated Vehicle Routing Problem (CVRP). Experimental results show that InstSpecHH demonstrates strong intra-subclass and inter-subclass generalization capabilities. Compared to previous problem-specific methods, InstSpecHH reduces the average optimality gap by more than 5.6\% for OBPP and 0.9\% for CVRP. These results highlight the potential of instance-aware automatic heuristic design to further enhance solution quality.
BibTeX
@misc{zhang2025llm,
  author = {Shaofeng Zhang and Shengcai Liu and Ning Lu and Jiahao Wu and Ji Liu and Yew-Soon Ong and Ke Tang},
  title = {{LLM-Driven Instance-Specific Heuristic Generation and Selection}},
  year = {2025},
  eprint = {2506.00490},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2506.00490},
}

Loading related content...

Figure