EDISCO: Equivariant DIScrete Diffusion for Euclidean Combinatorial Optimization

AI summary

Overview

Research area: Machine learning for combinatorial optimization, sitting at the intersection of geometric deep learning (E(2)-equivariant graph networks) and discrete diffusion generative modeling applied to routing problems such as the Traveling Salesman Problem (TSP) and the Capacitated Vehicle Routing Problem (CVRP).

Technical level: Advanced. The paper assumes familiarity with continuous-time Markov chains, categorical diffusion, group equivariance, quotient manifolds, and the standard neural combinatorial optimization benchmark protocol.

Scope: The paper proposes EDISCO, a discrete diffusion solver whose generative distribution over node-index solutions is exactly invariant under the two-dimensional Euclidean group E(2) by construction, rather than approximately so through data augmentation or symmetry regularization.

What This Paper Is About

Euclidean combinatorial optimization problems (ECOPs) such as TSP and CVRP are defined on coordinates in the plane, so rotating, reflecting, or translating an instance changes the input representation but never changes the correct node-index solution. Existing learning-based solvers only approximate this symmetry: they sample transformed copies of instances during training (orbit-sampling) instead of building the symmetry into the architecture (orbit-sharing), so the same local geometric pattern must be relearned in every coordinate frame it appears in. The goal of EDISCO is to build a diffusion model whose entire generative distribution over edge variables — score network, reverse sampler, and decoder — is exactly E(2)-invariant, so that the same local edge neighborhood always induces the same decision regardless of absolute position or orientation.

Key Contributions

1. Exact distribution-level E(2) invariance for generative ECOP solving. EDISCO's scalar edge, message, and node channels are constant on E(2) orbits, and the paper's Proposition 1 formalizes the induced reduction to the quotient space $X_{\mathrm{gp}}/G$ of dimension $2n-3$, with Corollary 2 stating the orbit-shared scalar representation that holds at every EGNN layer.

2. Efficient continuous-time categorical diffusion over discrete edge variables. Edge selection is formulated as a categorical CTMC (K = 2 states per edge) with closed-form forward transitions and exact posterior sampling, letting multi-step solvers such as PNDM and DEIS be adapted to discrete combinatorial variables for a quality–speed trade-off without retraining.

3. A native, symmetry-preserving decoder. Native Edge Expansion (NEE) converts the invariant edge-probability field into a feasible tour using only pairwise distances, edge probabilities, capacity-derived features, a partial edge set, and union-find connectivity — all coordinate-independent — so no external local-search refinement is needed and the invariance guarantee survives the final feasibility step.

4. Robustness under spatial and constraint shift. The same invariance principle is preserved under kNN sparsification and under capacity-conditioned CVRP features injected via FiLM, enabling transfer from uniform synthetic training to spatial out-of-distribution benchmarks and to a wide sweep of vehicle capacities with a single trained model.

Main Findings

• State-of-the-art TSP optimality gaps at lower training cost. At TSP-100/500/1000, EDISCO records lengths of 7.76, 16.55, and 23.24 with gaps of 0.000%, 0.018%, and 0.52% against Concorde (TSP-100) and LKH-3 (TSP-500/1000), and per-instance times of 0.075 s, 0.28 s, and 1.28 s. It is the fastest among the modern diffusion- and expansion-based solvers and leads on Gap at all three scales, while using only 33–50% of the training instances of competing diffusion methods.

• Better cross-size generalization. A TSP-1000-trained model (Figure 2) stays below 4.3% gap across all other scales, exceeding the cross-size generalization of DIFUSCO and T2T.

• Strong cross-distribution robustness. On the TSP-100 OOD protocol of Bi et al. (2022) with greedy + 2-opt decoding, EDISCO's average deterioration is 4% (Cluster 0.05% gap / 25% det., Explosion 0.03% / -25%, Implosion 0.05% / 13%), compared with 15% for GLOP, 133% for DIFUSCO, 687% for T2T, and 1961% for Fast-T2T.

• Leading CVRP gaps without external local search. Against HGS-CVRP at N ∈ {50, 100, 200, 500}, EDISCO achieves lengths 10.40, 15.60, 19.71, and 37.78 with gaps of 0.29%, 0.26%, 0.41%, and 1.70%, leading on Gap at all four scales and removing the local-search post-processing dependency.

• Capacity conditioning closes most of the constraint-shift gap. Across Q ∈ {10, 50, 100, 200, 300, 400, 500} on CVRP-100, the proposed capacity-conditioned model records gaps of 0.55, 0.26, 0.35, 0.45, 0.55, 0.65, 0.78, close to the per-capacity specialist upper bound (0.45, 0.26, 0.28, 0.35, 0.40, 0.45, 0.52) and far ahead of the same model with mixed but unconditioned training (1.50 to 1.70) or default-only training (up to 5.20 at Q = 10). Fixed-capacity baselines StruDiCO and NEXCO perform best at their training capacity Q = 50 and degrade rapidly away from it, while COExpander stays above 2% at every capacity.

• Data efficiency and tolerance of suboptimal labels. EDISCO achieves gaps below 0.07% with just 10% of TSP-50 training data, where DIFUSCO reaches 2.8% and T2T 2.1%. Trained on Farthest Insertion heuristic tours (average 7.5% gap to optimal on TSP-50), EDISCO reaches a 0.82% gap versus 2.75% for DIFUSCO and 1.35% for T2T under greedy decoding.

• Ablation confirms architectural orbit-sharing beats orbit-sampling. On TSP-500/1000, replacing the EGNN with a parameter-matched non-equivariant GNN nearly triples the gap (5.95% and 7.85% versus 2.10% and 3.05%), E(2) data augmentation recovers about half of the lost performance (4.10% / 5.45%), and a Sym-NCO soft equivariance loss trails further behind (4.85% / 6.55%).

• Sparsification preserves the guarantee. Dense adjacency is used for N ≤ 100 and kNN sparsification at larger scales; because neighbor sets depend only on pairwise Euclidean distances with deterministic index tie-breaking, the invariance argument carries over, and memory drops from O(n²) to O(kn), enabling training and inference on a single 48 GB GPU at all reported scales.

Methodology in Plain English

EDISCO treats solving a routing problem as a generative denoising problem over a matrix of binary edge decisions. Instead of predicting a tour directly, it starts from a fully random edge matrix and progressively cleans it up.

Corruption process. A continuous-time Markov chain (CTMC) flips edge variables at random with a linear rate schedule (β_min = 0.1 to β_max = 1.5 over t ∈ [0, 1]). Because the categorical CTMC has a closed-form transition probability, a noisy edge matrix at any time t can be sampled directly from a clean solution without simulating intermediate jumps.

Learned reverse process. The network is trained to predict the clean edge matrix from a noisy one (x₀ parameterization, chosen for stability near low-noise timesteps). Training minimizes edge-wise cross-entropy with a (1 − √t) weighting that emphasizes low-noise timesteps (Algorithm 1). CVRP capacity information is added as extra scalar inputs.

Equivariant score network. The core is an EGNN-style network that keeps node features, edge features, and messages as invariant scalars while letting coordinates transform equivariantly. Messages depend only on invariant quantities, most importantly the pairwise distance ‖x_i − x_j‖₂; coordinate updates are scalar-weighted relative vectors with w_ij = tanh(MLP_c(m_ij)/τ), τ = 10 and α = 0.1. Since the output head reads only invariant edge states, the predicted distribution over node-index edge variables is invariant under E(2). For CVRP, capacity enters only through invariant scalar channels (d_i/Q, (d_i + d_j)/Q, |d_i − d_j|/Q, and a global [log λ, Σ d_i/Q] embedding) that modulate scalar message channels via FiLM, leaving the coordinate update untouched.

Multi-step CTMC sampling. The continuous-time formulation allows the inference schedule to change without retraining. At each reverse step the network predicts x₀, Adams-Bashforth-style smoothing combines recent predictions into a smoothed probability p̃, and each edge is then sampled independently from an explicit categorical posterior kernel derived from the closed-form forward transitions (Equation 12).

Native Edge Expansion (NEE). The denoised edge-probability matrix is converted into a feasible tour by iteratively adding the highest-ranked feasible edge, ranked by r_ij = (P_ij + P_ji) / (2(d_ij + ε)). Feasibility is enforced with degree counts, a partial edge set, and union-find, allowing the Hamiltonian closure as the only cycle-closing step. For CVRP, the depot accepts one edge pair per active route, per-route accumulated demand is tracked, and candidate edges that would exceed capacity Q are rejected. All of these inputs and checks are coordinate-independent.

Experimental setup. TSP coordinates are uniform on [0,1]² with Concorde labels at TSP-100, LKH-3 labels at TSP-500/1000/10000, and the standard 1,280-instance and 128-instance test sets. CVRP uses integer demands {1, …, 9}, capacities Q ∈ {40, 50, 80, 100} for N ∈ {50, 100, 200, 500}, HGS-CVRP labels, and 10K/10K/100/100 test instances. Main results use 5-step DEIS-2 with NEE; TSP-10000 uses a 50-step PNDM quality variant. Additional experiments cover the Euclidean Steiner Tree Problem (ESTP) and Maximum Independent Set (MIS).

Why This Matters

Impact on research. The paper reframes equivariance in neural combinatorial optimization from a training-time trick (augmenting data with rotated and reflected copies) into an architectural and distributional property. It shows that for diffusion-based solvers, invariance must hold at the level of the whole generative pipeline — model, reverse sampler, and decoder — not just at the predicted output, and it supplies a formal quotient-space argument (Proposition 1) for why orbit-sharing should be more data-efficient than orbit-sampling. The empirical payoff is concrete: better gaps, faster inference, and dramatically smaller deterioration under distribution shift, all with 33–50% of the training instances.

Real-world applications:

• Last-mile and urban delivery routing, where customer locations come from arbitrary geographic coordinate frames and problem sizes and vehicle capacities vary across depots and fleets.
• Logistics and fleet management, where a single trained model must handle different vehicle capacities rather than one model per capacity setting — the constraint-shift experiment targets exactly this scenario.
• Field service and maintenance scheduling, where service points cluster unevenly in space (the Cluster OOD setting) rather than following the uniform distribution used for training.
• Real-world benchmark transfer, since the paper reports state-of-the-art results on real-world TSPLIB instances and evaluates under cross-distribution routing protocols.

Industry relevance. Practitioners deploying learned solvers face two practical obstacles the paper directly addresses: training labels are expensive and a deployed model's input distribution drifts away from its training distribution. EDISCO's insensitivity to suboptimal training labels (0.82% gap when trained on Farthest Insertion tours), its performance with only 10% of the training data, and its ability to run on a single 48 GB GPU via kNN sparsification all lower the barrier to deployment. Removing the external local-search step in the decoder also simplifies inference pipelines, and the reported per-instance times of 0.075 s at TSP-100 rising to 1.28 s at TSP-1000 are the kind of latency budgets production routing systems can plan around.

Future Directions

• Extending exact invariance beyond E(2). The paper's guarantee is specific to the planar Euclidean group. Whether the same orbit-sharing construction extends to three-dimensional routing or to problems whose symmetries are not Euclidean is not settled by this work.
• Scaling the constrained-routing regime. CVRP at N ∈ {1000, 2000} is handled only through a divide-and-conquer extension in Appendix A.2. It is not reported whether exact E(2) invariance is preserved through that decomposition, which is a natural follow-up question.
• Broadening the problem coverage. The paper tests ESTP and MIS in appendices to demonstrate generality. How the categorical edge-variable formulation and the invariant-feature principle transfer to other constraint structures, and whether the NEE decoder generalizes to them, remains open.
• Reconciling invariance with richer conditioning. Capacity conditioning here is restricted to invariant scalar channels so as not to break the guarantee. Whether more expressive constraint or objective conditioning (for example, time windows or heterogeneous fleets) can be added while preserving distribution-level invariance is an open design question.

Target Audience

Researchers and graduate students working on neural combinatorial optimization, discrete diffusion models, and geometric or equivariant deep learning will get the most from this paper, since it sits at the intersection of all three. It is also relevant to practitioners building routing and dispatch systems who care about out-of-distribution robustness, capacity flexibility, and inference latency, and to readers interested in how symmetry constraints can be enforced at the level of a generative distribution rather than through data augmentation. The paper is written at an advanced technical level: the method section assumes comfort with continuous-time Markov chains, group actions, and quotient manifolds, and the experimental section assumes familiarity with the standard TSP/CVRP benchmark conventions of the neural CO literature.

Authors’ abstract

Euclidean combinatorial optimization problems (ECOPs), such as the Traveling Salesman Problem (TSP) and Capacitated Vehicle Routing Problem (CVRP), possess inherent symmetries under the two-dimensional Euclidean group E(2), including rotations, reflections, and translations. Existing learning-based methods, including recent diffusion-based methods, rely on data augmentation or regularization to approximate E(2)-equivariance. This paper presents EDISCO, the first discrete diffusion model for ECOPs with exact E(2)-invariant generative distributions over node-index solutions. EDISCO introduces an E(2)-equivariant edge-score network coupled with a categorical continuous-time Markov chain over discrete edge variables, and exact posterior sampling provides efficient multi-step inference. This design gives EDISCO a local geometric inductive bias: edge neighborhoods with the same relative geometry and combinatorial context are represented consistently regardless of absolute position or orientation, making learning more efficient and inference more robust than non-equivariant methods. EDISCO outperforms previous learning-based state-of-the-art solvers on synthetic TSP from 100 to 10000 nodes and CVRP from 50 to 2000 customers, while using only 33-50% of the training instances. Trained only on uniform synthetic data, EDISCO also outperforms competing learning-based baselines under spatial distribution shift and CVRP constraint-tightness shift. Code is available at https://github.com/ValleyC/EDISCO.