[Paper] CoupleEvo: Evolving Heuristics for Coupled Optimization Problems Using Large Language Models

Source: arXiv - 2605.06341v1

Overview

The paper introduces CoupleEvo, a framework that leverages large language models (LLMs) to automatically generate and evolve heuristics for coupled optimization problems—situations where several interdependent sub‑problems must be solved together (e.g., routing plus scheduling, or layout plus resource allocation). By extending LLM‑driven heuristic design beyond single‑task scenarios, the authors show how coordinated evolutionary strategies can produce robust, high‑quality solutions for real‑world, multi‑facet challenges.

Key Contributions

• Three coordination strategies for evolving heuristics across coupled sub‑problems:
  1. Sequential – evolve a heuristic for one sub‑problem, then use its output as the starting point for the next.
  2. Iterative – alternate evolution of heuristics for each sub‑problem across successive generations.
  3. Integrated – evolve a single, joint heuristic that simultaneously addresses all sub‑problems.
• LLM‑augmented heuristic generation: prompts the LLM to synthesize candidate heuristic code snippets, which are then refined by an evolutionary loop.
• Empirical evaluation on two benchmark coupled problems, demonstrating that decomposition‑based strategies (sequential & iterative) converge more reliably and achieve better objective values than the integrated approach.
• Open‑source implementation (GitHub link) that lets practitioners plug in their own LLM back‑ends and problem definitions.

Methodology

1. Problem Decomposition – The target optimization task is expressed as a set of tightly linked sub‑problems (e.g., “assign tasks” + “schedule machines”).
2. Prompt‑Driven Heuristic Synthesis – An LLM (such as GPT‑4) receives a structured prompt describing a sub‑problem’s input, output, and performance metric. It returns a Python (or pseudo‑code) heuristic template.
3. Evolutionary Loop –
   • Population: each individual is a concrete heuristic (code) generated by the LLM, possibly with minor parameter tweaks.
   • Fitness Evaluation: run the heuristic on a set of problem instances; fitness is the combined objective across all sub‑problems.
   • Selection & Variation: standard genetic operators (mutation, crossover) are applied to the code (e.g., swapping lines, tweaking constants).
4. Coordination Strategies –
   • Sequential: evolve heuristics for sub‑problem A until convergence, freeze it, then evolve for sub‑problem B using A’s output.
   • Iterative: alternate evolution steps for A and B each generation, allowing feedback loops.
   • Integrated: treat the whole coupled problem as a single entity; the LLM generates a monolithic heuristic that is evolved as a whole.

The framework is modular: you can swap the LLM, change the evolutionary operators, or plug in a different optimizer for the evaluation step.

Results & Findings

Key takeaways

• Decomposing the coupled problem and coordinating evolution across sub‑problems yields more stable and higher‑quality solutions.
• The integrated approach suffers from a larger search space, making it harder for the evolutionary algorithm to find good heuristics.
• LLM‑generated heuristics are competitive with hand‑crafted baselines after only a few generations, highlighting the practical viability of LLM‑driven design.

Practical Implications

• Rapid Prototyping: Development teams can feed a high‑level description of a multi‑component optimization task to an LLM and obtain a working heuristic in minutes, then let CoupleEvo polish it automatically.
• Legacy System Integration: Companies with existing single‑task solvers can extend them to coupled scenarios without rewriting large codebases—just add the coordination layer.
• Scalable Automation: The framework can be run on cloud GPU/TPU instances, enabling large‑scale hyper‑parameter sweeps for logistics, cloud resource allocation, or manufacturing line balancing.
• Customization: Because the evolutionary loop works on actual code, developers can inject domain‑specific constraints (e.g., safety checks) as part of the fitness function, ensuring generated heuristics respect regulatory or performance limits.
• Open‑source Toolkit: The provided repository includes adapters for popular LLM APIs (OpenAI, Anthropic, LLaMA) and benchmark problem definitions, lowering the barrier for experimentation in industry labs.

Limitations & Future Work

• Search Complexity: The integrated strategy still struggles with high‑dimensional search spaces; future work could explore hierarchical or multi‑objective evolutionary algorithms to tame this complexity.
• LLM Dependence: Quality of initial heuristics hinges on the LLM’s training data; domain‑specific LLM fine‑tuning may be required for niche industries.
• Scalability to Many Sub‑Problems: Experiments covered only two coupled sub‑problems; extending to larger, more heterogeneous sets (e.g., > 5) may need smarter decomposition heuristics.
• Explainability: Evolved code can become opaque; integrating program analysis tools to surface why a heuristic works would aid adoption in safety‑critical domains.

Overall, CoupleEvo demonstrates that coordinated evolutionary search, powered by modern LLMs, is a promising route to automate heuristic design for the tangled optimization challenges that modern software systems face.

Authors

• Thomas Bömer
• Bastian Amberg
• Max Disselnmeyer
• Anne Meyer

Paper Information

• arXiv ID: 2605.06341v1
• Categories: cs.NE, cs.AI, math.OC
• Published: May 7, 2026
• PDF: Download PDF