UECO: A Unified Encoder with Structure-Aware Attention Mixture via Iterative Edge Evolving for Neural Combinatorial Optimization

Abstract

Despite the promise of Neural Combinatorial Optimization (NCO), recent literature has increasingly coupled *decision paradigms*, *training objectives*, and *problem classes* with specific backbone architectures, limiting generic model design and fair cross-paradigm evaluation. We propose UECO, a simple yet effective **U**nified **E**ncoder for **C**ombinatorial **O**ptimization with a structure-aware attention mixture scheme, where a lightweight module defined upon graph-based locality is interleaved with conventional (global) node-focused attention blocks to dynamically evolve edge representations and inject local topological information into attention scores. Instead of fusing static edge features in a single step, UECO thereby integrates local and global messages in a progressive and problem-agnostic manner. UECO is orthogonal to task-specific decoders, and works seamlessly with *Local Construction* (LC), *Global Prediction* (GP), and *Adaptive Expansion* (AE) paradigms, across node- or edge-oriented problems, symmetric or asymmetric tasks, and sparse or dense graphs, for supervised, reinforcement, or generative learning. Extensive experiments show that, via plug-in substitution of encoders, UECO consistently improves solution and generalization quality over diverse backbones and task scales on TSP, ATSP, CVRP, ACVRP, MIS, MaxClique, and MaxCut.