Cross-Domain Transfer of Learned Combinatorial Heuristics

38 concepts39 papers1 proposal

Combinatorial optimization problems—such as routing vehicles, scheduling factory floors, or solving Boolean satisfiability—are traditionally tackled using hand-crafted heuristics. In recent years, machine learning has introduced data-driven alternatives: neural networks, reinforcement learning agents, and large language models that automatically discover highly efficient optimization rules.

However, these learned solvers suffer from a fundamental limitation: domain lock-in. A neural network trained to solve the Traveling Salesman Problem (TSP) cannot easily solve a Job-Shop Scheduling problem, even though both are fundamentally about ordering sequences under constraints. Traditional machine learning models are brittle when faced with structural shifts because their parameters are tightly coupled to specific problem representations.

The frontier of cross-domain optimization transfer aims to break this barrier. The goal is to design frameworks, representations, and adaptation mechanisms that allow a heuristic learned on a source problem domain to generalize or adapt to a distinct target domain with minimal or zero retraining.


The Transferability Bottleneck in Combinatorial Spaces

In computer vision, a model pre-trained on natural images transfers easily to medical scans because low-level features like edges and textures are universal. In combinatorial optimization, however, features are deeply tied to the mathematical and geometric structure of the problem. A graph representation for a routing problem does not naturally map to the clause matrix of a Maximum Satisfiability (MaxSAT) problem.

Historically, understanding these boundaries involved mapping out where specific algorithmic behaviors break down. For instance, Weixiong Zhang in Phase Transitions of the Asymmetric Traveling Salesman demonstrated how sharp, predictable phase transitions occur as problem precision shifts, highlighting how tightly bound heuristics are to their exact problem distributions. Similarly, Haiou Shen et al. explored whether propagation-based lower bounds designed for Boolean satisfiability could maintain their pruning power when transferred to graph-based optimization via problem reduction, exposing a significant gap in cross-domain heuristic generalizability.

To achieve true cross-domain transfer, researchers must find a shared substrate—either in representation, adaptation mechanisms, or algorithmic structure—that transcends individual problem definitions.


Representation Pre-training and Structural Backbones

One intuitive way to enable transfer is to identify a "base problem" that captures the foundational geometric or relational properties of a broader class of problems. For spatial and routing tasks, the simple Traveling Salesman Problem (TSP) serves as an ideal foundation.

[Pre-train on Base Problem (e.g., TSP)] 
                 │
                 ▼  (Transfer Spatial Attention Backbones)
┌────────────────────────────────────────┐
│  Zero-Shot / Inference-Time Adaptation │
└───────────────────┬────────────────────┘
                    │
         ┌──────────┴──────────┐
         ▼                     ▼
[Target Domain A (CVRP)]   [Target Domain B (Orienteering)]

The authors of Cross-Problem Learning for Solving Vehicle Routing Problems leveraged this by pre-training a Transformer backbone on the simple TSP and then fine-tuning it for complex variants like the Capacitated Vehicle Routing Problem (CVRP) and the Orienteering Problem. This works because the core spatial attention mechanisms learned on the TSP capture universal principles of node proximity and route efficiency. These geometric priors remain highly relevant even when new constraints (like vehicle capacities or time windows) are introduced.

Taking this further, Haoyu Lei et al. introduced DIFU-Ada in Boosting Cross-problem Generalization in Diffusion-Based Neural Combinatorial Solver via Inference Time Adaptation. They demonstrated that a diffusion model trained on the TSP can adapt zero-shot to entirely different routing problems at inference time. By using energy-guided sampling to steer the generation process toward valid solutions for the new problem type, they bypass the need to alter the underlying model weights, effectively transferring structural routing priors across problem boundaries.


Meta-Learning and Dynamic Parameter Adaptation

When the mathematical structures of two domains are too distinct to share a direct representation, researchers instead transfer the strategy for adaptation. Rather than learning a static heuristic rule, the model learns how to observe its own progress and dynamically adjust its parameters on the fly.

This shift from transferring rules to transferring adaptation mechanisms is highly effective across varying problem landscapes:

Because the learning signal is based on the solver's current state and trajectory rather than the static features of the input instance, these meta-learning controllers maintain their utility when transitioning between structurally different combinatorial domains.


Symbolic Abstraction and Language-Driven Transfer

Another powerful mechanism for cross-domain transfer is translating neural insights into symbolic formulas or natural language principles. Neural network weights are notoriously difficult to transfer across different graph sizes or action spaces, but mathematical logic and language are universally interpretable.

Bo‐Cheng Lin et al. leveraged this in Automated design of state transition rules in ant colony optimization by genetic programming: a comprehensive investigation by using Genetic Programming to evolve explicit, interpretable state transition rules for Ant Colony Optimization (ACO). Because these rules are mathematical formulas rather than black-box weights, they possess an inherent structural clarity that makes them candidates for cross-domain evaluation.

Moving from symbolic formulas to natural language, frameworks like TIDE (Chentong Chen et al.) and HiFo-Prompt (ChentongChen et al.) use Large Language Models to distill abstract algorithmic design principles into a persistent knowledge base (referred to as "Hindsight").

[Problem Domain A] ──> [LLM Meta-Controller] ──> [Distilled Natural Language Principles]
                                                               │
                                                               ▼ (Cross-Domain Transfer)
[Problem Domain B] <── [LLM Meta-Controller] <─────────────────┘

By expressing optimization strategies as high-level concepts (e.g., balancing exploration and exploitation, or isolating independent subproblems) rather than code tied to a specific data structure, these frameworks lay the groundwork for transferring strategic insights across entirely different combinatorial domains.


Universal Algorithmic Substrates

Finally, cross-domain transfer can be achieved by embedding learned heuristics inside exact, classical optimization frameworks that already speak a universal mathematical language. Mixed-Integer Linear Programming (MILP) and Branch-and-Bound (BnB) trees look remarkably similar regardless of whether the underlying problem is a scheduling task, a network flow problem, or a portfolio optimization.

Max B. Paulus et al. exploited this in Learning To Dive In Branch And Bound by training Graph Neural Networks to learn "diving" heuristics based on LP duality theory. By tying the heuristic to the universal language of linear programming relaxations rather than the specific problem instance, the model learns pruning behaviors that transcend individual problem classes.

Similarly, the authors of A Learning Based Branch and Bound for Maximum Common Subgraph Related Problems integrated reinforcement learning into a BnB framework to dynamically learn branching choices based on search space reduction. When a heuristic learns to optimize the search tree itself rather than the problem variables, the potential for cross-domain transfer increases dramatically. This is also seen in hyper-heuristic frameworks like the one proposed by Li Shen 0008 et al. in Enhancing Column Generation by Reinforcement Learning-Based Hyper-Heuristic for Vehicle Routing and Scheduling Problems, where deep Q-networks select network-pruning heuristics within a universal Column Generation routine.

By targeting the shared mathematical machinery of exact solvers, learned heuristics escape the constraints of their training domain, moving closer to the ideal of general-purpose, data-driven optimization.

Key Foundational Work

Phase Transitions of the Asymmetric Traveling Salesman (2003) — contributed 1 concept elements to this direction.
Study of Lower Bound Functions for MAX-2-SAT (2004) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_cross_domain_optimization_transfer_9fce68fa,
  title = {cross-domain optimization transfer},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/cross-domain-optimization-transfer/rdr_9fce68fa2aeb46668354b4600f23c565},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_cross_domain_optimization_transfer_9fce68fa_v1,
  title = {cross-domain optimization transfer},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/cross-domain-optimization-transfer/rdr_9fce68fa2aeb46668354b4600f23c565/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake