🔢 mathematics

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

This paper introduces CoupleEvo, a Large Language Model-driven framework that employs three evolutionary coordination strategies to design heuristics for coupled optimization problems, demonstrating that decomposition-based approaches yield more stable and higher-quality solutions than integrated evolution.

Original authors: Thomas Bömer, Bastian Amberg, Max Disselnmeyer, Anne Meyer

Published 2026-05-08

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Thomas Bömer, Bastian Amberg, Max Disselnmeyer, Anne Meyer

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a massive, complicated puzzle. But here's the catch: this isn't just one puzzle; it's two (or more) puzzles that are glued together. If you move a piece in Puzzle A, it might break a piece in Puzzle B. To win, you can't just solve them separately; you have to solve them together, but doing everything at once is so confusing that your brain (or a computer) gets overwhelmed.

This paper introduces a new method called CoupleEvo. It uses a very smart AI (a Large Language Model, or LLM) to invent the "rules" or "strategies" (called heuristics) needed to solve these glued-together puzzles.

Here is how the paper explains it, using simple analogies:

The Problem: The "Glued" Puzzles

In the real world, many problems are "coupled."

Example 1 (The Delivery Driver): Imagine a company that needs to manage its warehouse stock and drive trucks to deliver goods. If you pack the warehouse perfectly but the trucks are too small to carry it, you fail. If you plan the truck routes perfectly but run out of stock, you also fail. You have to solve both at the same time.
Example 2 (The Robot Warehouse): Imagine a warehouse full of boxes where robots need to move items around. Some boxes are blocking others. A robot can't move Box A until it moves Box B. The "search for the right move" and the "planning the robot's path" are two different tasks that depend entirely on each other.

The Solution: The AI Coach

Instead of a human programmer writing the rules for how to solve these puzzles, the authors let an AI coach write the rules. The AI generates code (the "heuristic") that tells the computer how to explore different solutions.

The big question the paper asks is: How should we teach the AI to learn these rules when there are two glued-together puzzles?

The authors tried three different "teaching styles" (Evolutionary Coordination Strategies):

1. The "One-Thing-at-a-Time" Strategy (Sequential)

The Analogy: Imagine you are learning to play a duet on the piano. First, you practice only the left hand for a month until you are perfect. Then, you switch to the right hand and practice that for a month, keeping the left hand exactly as you left it.
What happened: The AI got really good at the first part very quickly. But when it switched to the second part, it struggled to improve because the first part was already "set in stone." It was like trying to fit a new right-hand melody to a left-hand part that was already too rigid. It worked well, but it hit a ceiling early.

2. The "Switching Back and Forth" Strategy (Iterative)

The Analogy: You practice the duet, but this time you switch hands every few minutes. You play the left hand, then the right, then the left again. You tweak the left hand to fit the right, then tweak the right to fit the left.
What happened: This was the most stable and reliable method. The AI didn't get stuck as easily. By constantly checking how the two parts fit together, it made steady, small improvements to both sides. It found the best overall balance, even if it didn't get to the "perfect" score as fast as the first method.

3. The "Do Everything at Once" Strategy (Integrated)

The Analogy: You try to learn the entire duet perfectly in one giant leap. You are trying to figure out the left hand, the right hand, and how they interact all in the same moment.
What happened: This was the most chaotic. Sometimes the AI got lucky and found a great solution. Other times, it got completely lost and produced terrible results. Because the "search space" (the number of possibilities) was so huge, the AI struggled to find a good path consistently.

The Results

The researchers tested these three methods on two real-world problems (the Delivery Driver and the Robot Warehouse).

The Winner: The "Switching Back and Forth" (Iterative) strategy was the most reliable. It consistently produced high-quality solutions that were very stable.
The Runner-up: The "One-Thing-at-a-Time" (Sequential) strategy was good but sometimes got stuck.
The Loser: The "Do Everything at Once" (Integrated) strategy was too risky; it was too unpredictable.

The Bottom Line

The paper shows that when you have a complex problem made of two interdependent parts, you shouldn't try to solve them all at once, nor should you solve them completely separately. The sweet spot is to evolve the solutions together, but by constantly switching your focus between the two parts.

The AI-generated strategies were good enough to beat some traditional human-made methods and came very close to beating the very best high-tech methods currently available, proving that AI can learn to write its own "rules of the game" for complex, glued-together problems.

Technical Summary: CoupleEvo

Problem Definition

Real-world optimization systems often consist of multiple tightly coupled subproblems where solutions must be coordinated to achieve high overall performance. These coupled problems frequently combine two or more NP-hard subproblems, such as in the Inventory Routing Problem (IRP) or the Multi-robot Multi-bay Unit-load Pre-marshalling Problem (MR-MUPMP). While optimizing subproblems in isolation often yields suboptimal global outcomes, fully integrated simultaneous optimization is frequently computationally intractable due to the combinatorial growth of the joint solution space.

Existing Large Language Model (LLM) driven automated heuristic design frameworks are currently limited to single-problem settings, evolving a single heuristic for a single objective. There is a gap in the literature regarding the systematic design of multiple interacting heuristics for coupled optimization problems, specifically lacking an evolutionary coordination strategy to manage the interdependencies between subproblems.

Methodology: CoupleEvo

The authors propose CoupleEvo, the first LLM-driven framework for automated heuristic design in coupled optimization problems. The framework operates within an iterative Large Neighborhood Search (LNS) context, where the LLM is tasked with generating destroy heuristics for each subproblem, while repair heuristics remain deterministic.

Evolutionary Coordination Strategies

CoupleEvo introduces three distinct strategies to govern the evolutionary search across interdependent subproblems:

Sequential Evolution: Heuristics are evolved for one subproblem after another. The evolution of subproblem $k$ proceeds for a fixed number of generations while all other subproblems use their current best-performing heuristics (fixed). This offers conceptual simplicity but risks premature convergence, where the first evolved heuristic constrains the search space for subsequent subproblems.
Iterative Evolution: The evolution alternates between subproblems over multiple control rounds. In each round, the algorithm cycles through all subproblems, refining their heuristics based on the best performers from the previous round. This strategy aims to prevent overfitting to a single subproblem and maintains flexibility for coordination.
Integrated Evolution: Heuristics for all subproblems are evolved simultaneously. The LLM is prompted to generate a full heuristic tuple (code and thoughts for all subproblems) in a single step. While this explicitly models interdependencies, it increases search complexity and places higher demands on the LLM's generative capabilities.

Implementation Details

LLM: The framework utilizes the open-source Qwen3-coder:30b model.
Prompting: The system employs a suite of prompt strategies adapted from prior work (EoH, ReEvo), including initialization (I1), exploration (E1, E2), and modification (M1, M2) prompts.
Evaluation: Fitness is calculated based on the objective value of the coupled problem instances. For IRP, fitness is the relative gap against a state-of-the-art HGS baseline; for MR-MUPMP, it is the average objective value.
Experimental Setup: The framework was tested on two domains:
- IRP: Integrating inventory management and vehicle routing.
- MR-MUPMP: Integrating move search (relocation sequencing) and vehicle routing with precedences.
- All strategies were allocated an equal evolutionary budget (40 total generations) to ensure fair comparison.

Key Contributions

CoupleEvo Framework: The formulation of the first LLM-driven framework extending automated heuristic design from single-problem settings to coupled optimization problems with multiple interdependent NP-hard subproblems.
Evolutionary Strategies: The proposal and systematic investigation of three coordination strategies (Sequential, Iterative, Integrated) that define how heuristics for interacting subproblems are generated and refined.
Comprehensive Evaluation: Extensive experimental evaluation on two representative coupled optimization domains, providing empirical insights into the trade-offs between convergence stability, search complexity, and solution quality.

Experimental Results

The study evaluated the three strategies across 6 runs per strategy for both IRP and MR-MUPMP.

Decomposition vs. Integration: Decomposition-based strategies (Sequential and Iterative) consistently demonstrated more stable convergence and higher solution quality compared to the Integrated strategy.
Sequential Strategy: Exhibited rapid initial fitness improvement when evolving the first subproblem. However, convergence often slowed or plateaued when switching to the second subproblem, suggesting that the first evolved heuristic constrained the search space. It achieved the best mean performance for MR-MUPMP.
Iterative Strategy: Showed a more gradual but consistently improving trajectory. By alternating focus, it mitigated premature overfitting and maintained adaptability. It achieved the best minimum and median fitness values for MR-MUPMP and the most stable results (smallest span) for IRP.
Integrated Strategy: Suffered from increased search complexity and high variability. While some runs achieved competitive results, the strategy generally exhibited weaker performance and larger variance, indicating difficulty in consistently refining high-quality heuristic tuples for coupled problems.

Benchmarking

The best-performing evolved heuristics (CoupleLNS) were compared against established literature:

IRP: CoupleLNS outperformed classical matheuristics (MH) by an average of 5.61%. It achieved competitive results against state-of-the-art Hybrid Genetic Search (HGS), with an average gap of 2.96%, without relying on extensive problem-specific engineering.
MR-MUPMP: Compared to a step-based sequential approach (SBS) using optimal A*, CoupleLNS had slightly lower solution quality on solvable instances but successfully solved all instances within the time limit, whereas SBS failed on some. When compared to an adapted SBS* (using an LLM-guided heuristic), CoupleLNS outperformed it by an average of 5.01%.

Significance and Claims

The paper claims that CoupleEvo demonstrates the potential of LLM-driven automated heuristic design for complex coupled optimization problems. The primary finding is that coordinating evolutionary search across interdependent subproblems is critical; decomposition-based strategies (sequential and iterative) are currently more effective than integrated evolution for these specific problem types.

The authors position their work not as a replacement for classical methods, but as a complementary approach. They suggest that LLM-based methods can evolve highly fitted, problem-specific heuristic components that enhance existing frameworks like LNS. The work highlights that while integrated evolution is theoretically appealing for capturing cross-component interactions, current LLM capabilities and search complexity favor strategies that decompose the problem while maintaining iterative coordination.

Future research directions identified by the authors include adapting the framework to problems with more than two subproblems, improving the stability of the integrated strategy, and developing adaptive coordination strategies that dynamically switch between optimization problems.