Technical Summary: CoEvo-AHD for Bi-Component Coupled Combinatorial Optimization

1. Problem Definition

The paper addresses Bi-Component Coupled Combinatorial Optimization (CO) problems, where a solution consists of two semantically distinct but interdependent decision components. The core challenge is that the feasibility or objective value of modifying one component depends entirely on the state of the other. Consequently, the utility of an operator is relational rather than intrinsic; an operator that performs well in isolation may degrade the global solution when coupled with a suboptimal state of the second component.

The authors instantiate this framework on two representative problems:

• Traveling Thief Problem (TTP): Couples routing (Traveling Salesman Problem) with packing (0–1 Knapsack Problem). The tour order affects travel speed based on carried load, while the packing plan determines the weight carried at each step.
• Traveling Purchaser Problem (TPP): Couples market selection/routing with procurement decisions. The visiting order and market selection determine feasible purchasing options and costs, while purchasing decisions influence the value of visiting specific markets.

Existing Large Language Model (LLM)-driven Automated Heuristic Design (AHD) methods typically evolve heuristics as isolated algorithmic units or search strategies (e.g., construction vs. repair). These methods fail to capture the problem-structure-induced complementarity required for bi-component coupled problems, where operators must be co-evolved to function synergistically across heterogeneous solution components.

2. Methodology: CoEvo-AHD

The authors propose CoEvo-AHD, an LLM-driven dual-population co-evolutionary framework designed to automatically discover and refine paired component operators. The framework operates through four stages:

2.1 Dual-Population Initialization

Two separate operator populations are maintained: $P_A$ for component A (e.g., route operators) and $P_B$ for component B (e.g., packing operators).

• Initialization: Populations start with a mix of manually specified seed operators and LLM-generated operators.
• Validation: All generated operators undergo syntax, interface, bounded execution, and component-feasibility validation before entering the population.
• Interface: Operators return candidate updates for their specific component only, relying on a shared information memory and external tools for global context.

2.2 Cooperative Evaluation

Unlike traditional methods that score operators in isolation, CoEvo-AHD evaluates operators through paired execution on complete solutions.

• Selection: A local Thompson Sampling strategy selects one operator from $P_A$ and one from $P_B$ for each search restart.
• Alternating Optimization: The selected pair is invoked alternately within a search trajectory. For example, a route operator proposes a city permutation, which is then passed to a packing operator (or vice versa).
• Repair & Reconstruction: Because components are coupled, intermediate candidates may be infeasible. The framework utilizes a tool-augmented problem environment to perform feasibility repair, reconstruction, and full-objective evaluation.
• Shared Information: A mutable dictionary (shared_info) allows operators to exchange soft search signals (e.g., load profiles, candidate insertion cues) without directly overriding the other component's logic.

2.3 Population Management & Evolution

The framework employs a co-evolutionary loop to refine the populations:

• Scoring: Rewards are computed based on the improvement of the complete coupled solution. These rewards update three statistics: individual scores for $o_A$ and $o_B$, and a pairwise synergy score ($S_{ij}$) for the specific operator pair.
• Pruning: Low-performing operators are removed from their respective populations.
• LLM-Driven Evolution: Vacancies are filled via three evolutionary operations:
  1. Intra-component Mutation: Refines a single parent operator.
  2. Intra-component Homogeneous Crossover: Recombines two operators from the same population.
  3. Cross-Component Joint Crossover: Selects the best-performing pair $(o_A^*, o_B^*)$ based on synergy scores and prompts the LLM to rewrite them as a unified, coordinated entity. This encourages the generation of operators with compatible communication protocols and complementary search assumptions.

2.4 Tool-Augmented Environment

To prevent LLMs from generating inefficient or error-prone low-level code, the framework encapsulates core operations (e.g., local-search delta computation, greedy reconstruction, feasibility checks) into standardized callable tools. This allows LLM-generated operators to focus on high-level neighborhood design and cross-component coordination.

3. Key Contributions

1. Problem Formulation: The paper formulates LLM-driven AHD specifically for bi-component coupled CO, defining operator utility as relational and necessitating joint assessment across heterogeneous solution components.
2. CoEvo-AHD Framework: A novel co-evolutionary architecture featuring:
   • Component-specific operator populations.
   • Paired execution-based evaluation to capture cross-component interactions.
   • Pairwise synergy scoring to guide the selection of complementary operator pairs.
   • Cross-component joint crossover to evolve mutually compatible operators.
3. Structured Communication & Tooling: The introduction of a structured inter-component communication protocol and a tool-augmented environment that standardizes problem-specific operations, enabling LLMs to generate robust, high-level heuristic logic.

4. Experimental Results

The framework was evaluated on TTP and TPP benchmarks against state-of-the-art traditional heuristics and recent LLM-based baselines.

• Traveling Thief Problem (TTP):

  • CoEvo-AHD achieved the best results on small-to-medium instances (TTP20, TTP50), outperforming baselines like MATLS, S5, and CoCo.
  • On larger instances (TTP100, TTP200), it achieved the second-best overall average, trailing only CoCo but significantly outperforming MATLS and S5.
  • This suggests the framework effectively captures coupling in smaller search spaces but faces challenges in search depth for very large instances.

• Traveling Purchaser Problem (TPP):

  • CoEvo-AHD demonstrated a pronounced overall advantage, achieving the best results on five instance scales (including large scales like 150×100 and 150×150) and second-best on three others.
  • It reduced the average objective value by approximately 2.76% compared to the second-best baseline (TA) and up to 11.42% compared to ALNS.
  • The results indicate the framework is particularly effective at exploiting the synergy between routing and procurement decisions in TPP.

• Ablation Studies:

  • Removing the dual-population co-evolution (evolving only one component) caused significant performance degradation (e.g., ~11% drop on TPP), confirming that optimizing components in isolation is insufficient.
  • Removing the tool-augmented environment also led to performance drops (~5.5% on TTP), highlighting the importance of standardized interfaces for reliability and efficiency.

5. Significance and Claims

The paper claims that CoEvo-AHD represents a shift in LLM-driven AHD from generating isolated algorithmic roles to modeling problem-structure-induced operator complementarity. By explicitly co-evolving heterogeneous operator populations and evaluating them through joint execution, the framework addresses the limitation of existing methods that cannot handle strong coupling between decision substructures.

The authors position this work as a step toward more generalizable automated heuristic design for complex, real-world optimization problems where solution components are deeply interdependent. They modestly note that while the framework is highly competitive, there remains room for improvement in search depth and robustness for very large-scale instances, and future work will aim to extend the framework to problems with more than two coupled components.