PaperlayerView exact revision on arXiv

Source-linked AI summary

G-LNS: Generative Large Neighborhood Search for LLM-Based Automatic Heuristic Design

Baoyun Zhao, He Wang, Liang Zeng

arXiv:2602.08253v1cs.AI

TL;DR

Existing LLM-based AHD methods are constrained by fixed heuristic forms, limiting structural exploration in complex COPs. G-LNS co-evolves coupled destroy and repair LNS operators with cooperative evaluation, and it outperforms AHD and classical baselines while generalizing across unseen distributions.

  • Problem

    Existing AHD methods typically use constructive rules or fixed local-search templates, limiting the search space's capacity for structural exploration.

  • Method

    G-LNS uses LLMs to co-evolve executable destroy and repair LNS operators, evaluating their interaction through synergy-aware cooperative evolution.

  • Results

    G-LNS outperforms LLM-based AHD methods and strong classical solvers on TSP and CVRP, achieving near-optimal solutions with reduced computational budgets.

  • Takeaways & Limitations

    The evolved operators demonstrate robust generalization across diverse and unseen instance distributions, including held-out and benchmark routing datasets.

Abstract

from arXiv · show

While Large Language Models (LLMs) have recently shown promise in Automated Heuristic Design (AHD), existing approaches typically formulate AHD around constructive priority rules or parameterized local search guidance, thereby restricting the search space to fixed heuristic forms. Such designs offer limited capacity for structural exploration, making it difficult to escape deep local optima in complex Combinatorial Optimization Problems (COPs). In this work, we propose G-LNS, a generative evolutionary framework that extends LLM-based AHD to the automated design of Large Neighborhood Search (LNS) operators. Unlike prior methods that evolve heuristics in isolation, G-LNS leverages LLMs to co-evolve tightly coupled pairs of destroy and repair operators. A cooperative evaluation mechanism explicitly captures their interaction, enabling the discovery of complementary operator logic that jointly performs effective structural disruption and reconstruction. Extensive experiments on challenging COP benchmarks, such as Traveling Salesman Problems (TSP) and Capacitated Vehicle Routing Problems (CVRP), demonstrate that G-LNS significantly outperforms LLM-based AHD methods as well as strong classical solvers. The discovered heuristics not only achieve near-optimal solutions with reduced computational budgets but also exhibit robust generalization across diverse and unseen instance distributions.

1. Introduction

Existing LLM-based AHD methods often search within fixed constructive or local-search forms, limiting structural exploration. G-LNS addresses this bottleneck by co-evolving destroy–repair LNS operators and demonstrates strong performance and generalization on routing benchmarks.

  • Motivation: Existing AHD methods commonly evolve constructive priority rules or tune parameters within fixed neighborhood structures, restricting structural exploration.Constructive decisions are difficult to reverse, while fixed neighborhoods limit LLMs to parameter adjustment.
  • Method: Large Neighborhood Search alternates structural destruction and reconstruction, making complementary destroy–repair logic central to effective automated design.The destroy phase creates defects that the repair phase must specifically reconstruct.
  • Method: G-LNS extends LLM-based AHD to automatically design executable Large Neighborhood Search destroy and repair operators.The framework moves beyond constructive rules and fixed local moves toward structural solution perturbation.
  • Method: G-LNS jointly evaluates destroy and repair operators through cooperative co-evolution, explicitly modeling their coupling with a synergy matrix.The mechanism guides synergy-aware crossover toward complementary operator logic.
  • Results: G-LNS outperforms LLM-based AHD methods and strong classical solvers on TSP and CVRP, achieving near-optimal solutions with substantially reduced computational budgets.The experiments also report robust generalization across diverse and unseen instance distributions.

2. Background

AHD searches a discrete space of heuristics mapping problem instances to solutions, but fixed parameterizations constrain the search dynamics. This work formulates LNS operator design as optimization over executable destroy and repair code.

  • Automatic Heuristic Design: Automatic Heuristic Design seeks high-performance heuristics for COPs by identifying a heuristic that minimizes expected objective value over a target instance distribution.A heuristic is modeled as a mapping from instance space I to solution space S within a discrete algorithm space H.
  • Automatic Heuristic Design: The expressiveness of AHD depends on heuristic parameterization, and predefined templates can prevent fundamental changes to search dynamics.The paper therefore focuses on structurally adaptive search operators rather than fixed heuristic forms.
  • Large Neighborhood Search: LNS iteratively destroys part of a solution and repairs the resulting partial solution to explore the solution space.Given x, destruction produces x_partial and repair produces a complete solution x′.
  • Large Neighborhood Search: LNS performance depends on coupling destruction with repair so that targeted disruption is followed by efficient reconstruction.Complementary operator-pair design remains a central challenge motivating automation.
  • Problem Formulation: The paper formulates automated LNS operator design as optimization over discrete executable-code spaces for destroy and repair operators.A policy π=(d,r) is evaluated by running an LNS algorithm with inherent stochasticity on instances sampled from D.
  • LLM-based AHD: LLM-based evolutionary AHD methods use language models as variation operators to generate heuristic code from prior implementations and performance feedback, often within fixed templates.This establishes the thought–code co-evolution setting that G-LNS extends.

3. Methodology

G-LNS automates LNS operator discovery through LLM-driven evolutionary search over separate destroy and repair populations. Adaptive evaluation measures individual operator quality and pairwise synergy, guiding pruning and several variation strategies, including synergy-conditioned joint crossover.

  • Framework Overview: G-LNS treats heuristic design as evolutionary search over algorithmic structures, with LLMs generating variation beyond fixed heuristic templates.The framework uses an adaptive scoring mechanism to quantify the contribution of generated operators.
  • Initialization: The framework maintains separate destroy and repair populations, seeded with domain heuristics and tracked through fitness, synergy, and adaptive-weight structures.For TSP/VRP, example seeds include Random Removal, Worst Removal, and Greedy Insertion.
  • Evaluation: Across multiple independent episodes, adaptive LNS selects operator pairs, scores their solution updates, and accumulates global fitness and synergy statistics.Adaptive weights reset between episodes, while global fitness and synergy statistics accumulate to reduce single-episode stochasticity.
  • Evaluation: The evaluation updates adaptive weights, global operator fitness, and the synergy matrix to support search guidance, population management, and cooperative evolution.High synergy values identify complementary destroy–repair pairs for subsequent joint crossover.
  • Population Management: After every K episodes, G-LNS ranks both populations by accumulated fitness and removes the bottom M operators before replenishing the vacancies.Pruning preserves high-performing elites and creates slots for LLM-driven evolution.
  • Evolution: Evolution combines rank-adaptive mutation, same-type crossover, and synergy-guided joint crossover to generate refined or structurally coupled operators.Joint crossover conditions repair generation on destroy logic so reconstruction is tailored to the defects introduced by destruction.
  • Robustness and Reset: Generated operators pass sanity and complexity checks, while resetting fitness and synergy after replenishment prevents historical scores from dominating the next cycle.Invalid operators trigger regeneration, and newly generated operators begin the next cycle on equal footing with surviving elites.

4. Experiments

Experiments evaluate G-LNS across routing problems, held-out and real-world distributions, efficiency comparisons, convergence behavior, and component ablations. G-LNS generally delivers strong solution quality, scalability, computational efficiency, and generalization.

  • Experimental Setup: G-LNS is evaluated across TSP, CVRP, and OVRP using held-out generated instances and TSPLib and CVRPLib benchmarks.Evolution uses randomly generated instances, while testing includes both held-out and established benchmark datasets.
  • Synthetic Held-Out Instances: G-LNS consistently achieves the lowest optimality gaps among LLM-driven methods on TSP, especially at TSP100 and TSP200.The evolved operators dynamically adjust destruction magnitude and exploration noise according to real-time solution states.
  • Synthetic Held-Out Instances: On CVRP100 and CVRP200, G-LNS outperforms LLM-based baselines and identifies solutions superior to OR-Tools as capacity-constrained complexity increases.The learned destroy-and-repair operators can correct structural defects that constructive methods struggle to address.
  • Computational Efficiency: G-LNS requires 3.23s to 280.91s across CVRP10–CVRP200, versus 84.16s to 2407.14s for MCTS-AHD, while exceeding benchmark solution quality.The OR-Tools evaluation uses a fixed 320-second batch budget and leaves a 1.27%–2.09% gap.
  • Generalization: G-LNS reduces CVRPLib Set F’s optimality gap from 40.1% with EoH-S to 15.9% and maintains a 2.8% gap on TSPLib.These results are reported as evidence of generalization across distributions differing from those used during evolution.
  • Ablation Studies: Ablations show that removing mutation, homogeneous crossover, synergistic crossover, or adaptive weights degrades solution quality.The results specifically associate synergistic crossover with destroy-repair coupling and adaptive weights with useful feedback.
  • Convergence Analysis: Across 200 generations, operator quality improves rapidly early and then refines steadily, while CVRP100 evaluation reaches a superior solution in approximately 70 seconds.G-LNS reaches an objective of approximately 13.8 versus approximately 14.1 for OR-Tools and requires 70 seconds versus 320 seconds.

5. Conclusion

The paper positions G-LNS as a generative evolutionary approach addressing structural limits in automated heuristic design. It concludes that co-evolved destroy-and-repair operators outperform established alternatives on routing problems, while identifying broader optimization settings for future study.

  • Conclusion: G-LNS co-evolves tightly coupled destroy and repair operators through synergy-aware evaluation and evolutionary variation strategies.The framework automates discovery of high-performance LNS operators beyond fixed heuristic templates.
  • Conclusion: G-LNS outperforms state-of-the-art baselines and strong classical solvers on complex routing problems while demonstrating superior generalization.The paper proposes extending the framework to multi-objective optimization and combinatorial problems beyond routing.
  • Background: AHD searches for high-quality heuristic algorithms in an algorithm space rather than directly searching for solutions in the solution space.The objective includes generalization across a target distribution of problem instances rather than fitting a single case.
  • Prior AHD Limitations: Traditional genetic-programming AHD depends on hand-crafted mutation and crossover operators that require domain expertise for valid, meaningful heuristic changes.This dependency motivates more generative approaches to algorithm discovery.
  • Neural Combinatorial Optimization: NCO methods learn heuristics offline for fast inference but can suffer from black-box behavior and poor generalization under unseen scales or distributions.These limitations motivate LLM-based AHD, which evolves explicit algorithmic code instead of opaque neural weights.

A.3. LLM for Combinatorial Optimization

LLM-based combinatorial optimization has shifted from direct solution generation toward executable heuristic design, but many methods remain constrained by fixed forms. G-LNS instead targets structurally adaptive LNS operators that reshape solutions through destroy–repair search.

  • LLM paradigms: LLM-based CO methods are commonly organized into LLM-as-Solver and LLM-as-Designer paradigms.The former generates or iteratively refines solutions, whereas the latter generates executable heuristic code.
  • LLM as Solver: Direct LLM solving struggles with numerical reasoning, rigorous backtracking, hallucinations, and scaling to large instances.These limitations motivate approaches that execute generated code rather than relying on direct inference.
  • LLM as Designer: Existing AHD methods use reflective evolution, Monte Carlo Tree Search, or complementary heuristic sets to improve exploration and cross-distribution coverage.These approaches still generally evolve heuristics within established algorithmic forms.
  • Structural design: G-LNS differs from LHNS and prior AHD by designing structural destroy and repair operators instead of only optimizing heuristic functions, parameters, or code blocks.This enables complex topological transformations of solutions rather than guidance within a fixed solver skeleton.
  • LNS foundation: LNS alternates large-scale destruction and reconstruction, allowing substantial solution reshaping beyond small local-search moves.In TSP, destroy removes cities from a tour and repair reinserts them; analogous route restructuring applies to CVRP.

C.1. Dataset Generation and Benchmarks

The study discovers operators on a compact fixed-size training set, then evaluates them across multiple scales, generated distributions, and standard routing benchmarks.

  • Training set: Operator discovery uses 16 training instances with fixed size N = 50 to encourage generalizable logic rather than overfitting to massive datasets.The discovery set is deliberately compact and scale-specific.
  • Testing set: Testing uses 64 held-out instances at each scale N ∈ {10, 20, 50, 100, 200} to assess performance and scalability.The design tests whether operators learned at N = 50 transfer to both smaller and larger instances.
  • Instance generation: TSP instances sample node coordinates uniformly from the unit square [0, 1]^2.
  • Instance generation: CVRP and OVRP use coordinates from [0, 1]^2, demands uniformly sampled from {1, ..., 9}, and vehicle capacity Q = 50.The CVRP depot is fixed at (0.5, 0.5).
  • Benchmark evaluation: Cross-distribution generalization is additionally evaluated on TSPLib and CVRPLib benchmark datasets.

C.2. Implementation Details

The experiments use official or author-provided baseline implementations and matched LLM settings to make performance differences reflect algorithmic structure.

  • Classical baselines: LKH-3 is run through its official executable with default parameters for TSP comparisons.
  • Neural baseline: POMO uses the authors’ pretrained models with greedy decoding and batch size = 1 to measure raw inference speed without augmentation.
  • ALNS baseline: ALNS uses classic removal and insertion portfolios with standard adaptive-weight and simulated-annealing settings.The portfolio includes random, worst, related, greedy, and regret-k operators.
  • LLM-based baselines: LLM-based AHD baselines are reproduced with the same DeepSeek-V3.2 backend and prompt settings described in their papers.This controls for language-model capability when comparing algorithm structures.

C.3. Evaluation Budget and Efficiency

G-LNS is evaluated under a sharply reduced interaction budget and uses structured evolutionary actions to generate, refine, recombine, and jointly evolve destroy–repair operators.

  • Budget: G-LNS uses 200 generations, compared with 1,000 generations typically used by existing LLM-based AHD methods.This corresponds to 20% of the baseline interaction budget.
  • Efficiency: Despite using 20% of the interaction budget, G-LNS achieves superior performance and reduces LLM queries, token consumption, and operational costs.The paper attributes this efficiency to evolving high-level structural operators rather than low-level constructive rules.
  • Initialization: Initialization prompts create valid destroy and repair operators to populate the two heuristic pools when expert seeds are insufficient.Destroy operators perturb complete solutions, while repair operators reconstruct solutions from partial ones.
  • Mutation: Adaptive mutation applies logic evolution to lower-ranked operators and parameter calibration to top-ranked operators.Intermediate-ranked operators receive a strategy stochastically.
  • Crossover: Homogeneous crossover combines two same-type parents by preserving Parent 2’s structure while incorporating Parent 1’s high-level logic.Parents are selected by roulette-wheel sampling using historical fitness.
  • Crossover: Synergistic joint crossover selects destroy–repair pairs using accumulated synergy scores and prompts the LLM to co-evolve them as a unified entity.The strategy addresses the structural dependency between destruction and reconstruction.

E.1. Discovered Operators for TSP

For TSP, G-LNS evolves paired operators that adapt destruction and repair to solution state and perturbation intensity. The discovered ACSR–DAPI pair combines structural disruption with diversity-aware reconstruction.

  • Discovered operators: G-LNS evolved ACSR and DAPI as a state-dependent destroy–repair pair for TSP.ACSR denotes Adaptive Continuous-Segment Removal, while DAPI denotes Diversity-Adaptive Probabilistic Insertion.
  • Destroy operator: ACSR removes one expensive continuous segment for moderate perturbations and switches to multi-segment fragmentation for aggressive destruction.This magnitude-dependent strategy is designed to refine local connections while preventing structural lock-in.
  • Repair operator: DAPI monitors solution diversity and adjusts its Softmax temperature and exploration threshold accordingly.Low diversity increases randomness and temperature, while higher diversity supports more focused insertion choices.
  • Destroy operator: The TSP implementation supports continuous, multi-segment, and fallback random removal while preserving the requested destruction count.Removed indices are sorted before deletion, and additional random removal fills any shortfall.
  • Repair operator: DAPI inserts removed cities using random exploration or probabilistic cost-based selection, followed by diversity-dependent 2-opt search.Insertion costs are computed for every possible position, and the exploration probability is controlled by the observed diversity.

F.1. Details on OVRP

On OVRP, G-LNS is evaluated against OR-Tools and LLM-based methods across five problem sizes. It remains competitive at smaller scales and scales better on the largest instances, where constructive baselines deteriorate sharply.

  • Experimental setup: OVRP evaluation compares G-LNS with OR-Tools and LLM-based AHD methods across five problem sizes.The results are reported in Table 4, with gaps measured against the best solution found among all methods.
  • Performance: At N = 200, G-LNS reduces objective cost from 15.19 for OR-Tools to 14.88, achieving Gap 0.00%.OR-Tools yields a 2.05% gap under the computational time limit, whereas G-LNS establishes a new best-known frontier.
  • Performance: Constructive LLM-based baselines show optimality gaps exceeding 30% for OVRP instances with N ≥50.Their sequential decision-making does not adapt effectively to the open-route structure.

F.2. Details on Benchmarks

On TSPLib and CVRPLib benchmarks, G-LNS outperforms the compared baselines across all benchmark sets. Its operators operate on raw instance data rather than normalized coordinates.

  • Benchmark results: The benchmark comparison includes EoH, ReEvo, and the heuristic-set method EoH-S.The evaluation covers both Traveling Salesman Problem and Capacitated Vehicle Routing Problem benchmark families.
  • Benchmark results: G-LNS outperforms all baselines across the TSPLib and CVRPLib benchmark sets.Table 5 reports average optimality gaps across instances within each benchmark category.
  • Evaluation protocol: Baseline methods use normalized node coordinates mapped to [0, 1], with gaps calculated relative to best-known LKH-3 solutions.This protocol follows the EoH-S evaluation configuration.
  • Evaluation protocol: G-LNS operates directly on raw, unnormalized instance data rather than the normalized coordinates used by the baselines.The paper presents this as evidence that its evolved operators capture routing topology independently of coordinate scale.
  • Benchmark results: Detailed benchmark gaps are reported separately for TSPLib and CVRPLib dataset groups.TSPLib results appear in Table 6, while CVRPLib results cover Sets A, B, E, F, M, P, and X.
Loading 2602.08253v1…