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.
Figures & tables
Figure 1: EDISCO’s EGNN architecture. EGNN layers update coordinates equivariantly and output edge probabilities that remain invariant under rotations, reflections, and translations.
Figure 2
Figure 2: Cross-size generalization for TSP models trained at one scale and evaluated across all scales under greedy decoding.
Figure 3: EDISCO tours on Uniform and three OOD distributions for TSP-100.
Figure 4: TSP-50 performance under training-data variations. Left: optimality gap as a function of training set size. Right: performance comparison when trained on optimal data versus heuristic Farthest Insertion data.
Table 6
Appendix figures & tables9 assets
Supplementary material from the paper’s appendix.
Appendix
Method
Type
Length ↓
Gap ↓
Time ↓
Reference Solvers
LKH-3 [ Helsgaun, 2017 ]
Heuristic
71.77
0.00%
248 s
2-opt [ Croes, 1958 ]
Heuristic
91.16
27.02%
13.4 s
Farthest Insertion
Heuristic
80.59
12.36%
6.2 s
Non-Generative Neural Solvers
AM [ Kool et al., 2019 ]
RL+G
141.51
97.17%
3.6 s
Appendix
Table 11: TSP-10000 results. Gap is relative to LKH-3 (default). Time is per-instance wall-clock measured at batch size 1, single-thread, on the hardware described in Appendix E.2 ; all Time entries are re-measured under this protocol following Wang et al. [2025] , Wang et al. [2026] . Best and second-best marked per Gap and Time column among solvers achieving sub- 2% Gap (faster low-quality solvers such as GLOP at 4.90% and AM at 97.17% are excluded from the ranking). RL: reinforcement learning, SL: supervised learning. G: greedy, 2O: 2-opt, S: sampling, AS: active search, AE/NAE/NEE: adaptive / native adaptive / native edge expansion. “–”: solver does not extend to this scale.
Schedule
Configuration
Optimality Gap (%)
Conv.
Inference
Type
Best
Final
Epoch
Time (s)
Linear
Aggressive: β∈[0.1,2.0]
2.88
3.03
50
1.06
Baseline: β∈[0.1,1.5]
2.29
2.63
45
1.06
Conservative: β∈[0.1,1.0]
2.74
3.51
50
1.16
Exponential
Baseline: a =0.5, b =4.0
3.39
3.60
50
1.04
Conservative: a =0.3, b =3.0
4.19
4.42
50
1.13
Appendix
Table 13: Comparison of noise schedules for TSP diffusion on TSP-50. All models trained for 50 epochs with 50 diffusion steps. Bold indicates the lowest gap and inference time.
Step Size α
0.01
0.05
0.1
0.2
0.5
Optimality Gap (%)
0.08
0.03
0.01
0.15
Diverged
Coordinate Std ∗
0.42
0.38
0.35
0.18
0.02
Training Stable
✓
✓
✓
Unstable
Collapsed
Convergence Epoch
42
38
35
48
-
Appendix
Table 14: Effect of step size α on model performance and training stability (TSP-50). ∗ Standard deviation of coordinates after 8 layers (optimal range: 0.3-0.4).
Temperature τ
1
5
10
20
50
Optimality Gap (%)
0.12
0.04
0.01
0.02
0.05
Avg. Gradient Norm †
0.003
0.018
0.042
0.038
0.031
Tanh Saturation Rate ‡
68%
24%
8%
12%
18%
Convergence Epoch
52
40
35
36
39
Appendix
Table 15: Effect of temperature τ on gradient flow and performance (TSP-50). † Average gradient norm in coordinate MLP during first 10 epochs. ‡ Percentage of tanh outputs with ∣wij∣>0.95 .
Table 16: Joint ablation of α and τ on TSP-100 (optimality gap %).
Method
Model
Training Instances (K) / Optimality Gap (%)
Parameters
TSP-50
TSP-100
TSP-500
TSP-1000
TSP-10000
DIFUSCO †
5.3M
1500 / 0.48
1500 / 1.01
128 / 9.41
64 / 11.24
6.4 / 8.95
DISCO †
5.3M
1500 / 0.16
1500 / 0.58
- / -
- / -
6.4 / 2.90
T2T ∗
5.3M
1500 / 0.04
1500 / 0.18
128 / 5.09
64 / 8.87
6.4 / 2.92
EDISCO-Full
5.5M
500 / 0.01
500 / 0.04
60 / 1.95
30 / 2.85
3 / 1.98
EDISCO-Medium
1.9M
500 / 0.03
500 / 0.08
60 / 2.18
30 / 2.85
3 / 2.43
Appendix
Table 17: Model efficiency and performance comparison across TSP scales. Training instances shown in thousands (K) with corresponding optimality gaps (%). All EDISCO entries use 50-step PNDM with greedy decoding (no NEE, no 2-opt) so capacity differences across architectures are isolated from sampler and decoder effects; the main-table SL+NEE configuration of Table 1 therefore reaches lower gaps than the EDISCO-Full row here. EDISCO-Full uses 12 EGNN layers with 256 hidden dimension (5.5M parameters), EDISCO-Medium uses 12 layers with 128 hidden dimension (1.9M parameters), and EDISCO-Small uses 8 layers with 128 hidden dimension (1.3M parameters). † 12-layer GNN with width 256. ∗ Same architecture as DIFUSCO.
Figure 6: Five rounds of the denoising process of EDISCO on the original TSP instance.
Figure 7: Five rounds of the denoising process of EDISCO on the 45∘ rotated instance.
Figure 8: Five rounds of the denoising process of EDISCO on the 90∘ rotated instance.
Diffusion-based neural solvers have shown strong promise for combinatorial optimization (CO), but existing methods typically rely on supervised training with large collections of near-optimal solutions. In this work, we extend adjoint-based trajectory optimization methods to discrete combinatorial domains. We formulate diffusion-based CO as a stochastic control problem over Continuous-Time Markov Chains and introduce discrete adjoint dynamics for propagating optimization signals through discrete generative trajectories. Building on this formulation, we propose Combinatorial Adjoint Matching (CAM), an unsupervised training framework for discrete diffusion solvers with structured and low-variance trajectory-level optimization signals. Empirically, CAM consistently outperforms existing unsupervised diffusion baselines and achieves performance competitive with strong supervised diffusion solvers and even traditional solvers across diverse combinatorial optimization problems. Our code is available at https://github.com/Shengyu-Feng/CAM.
Shengyu Feng, Tarun Suresh, Yiming Yang
Language Technologies Institute, Carnegie Mellon University · University of Illinois Urbana-Champaign
Neural combinatorial optimization has recently achieved strong results on the Euclidean Traveling Salesman Problem (TSP) using generative models such as diffusion and consistency models. State-ofthe-art approaches like FT2T combine fast consistency-based prediction with gradient-based inference time refinement. However, gradient search often incurs significant computational overhead and may not align with the discrete structure of feasible solutions. We introduce Projected Consistency Inference (PCI), a plug-and-play, retraining-free alternative that replaces gradient refinement with structure-aware projections: PCI decodes valid Hamiltonian tours from the consistency model output and applies a lightweight local search (e.g., 2-opt). PCI achieves an average optimality gap (OG) of 0.17% on TSP with 500 cities, and 0.31% on TSP with 1000 cities, outperforming FT2T best settings (OG 0.22% and 0.36%, respectively) while reducing the inference time up to 30 to 40%. PCI also exhibits lower variance and memory usage, and can surpass classical heuristics such as LKH3 in rapid solution generation. Our results demonstrate that structure-aware inference time operations provide a practical and principled path for neural TSP solvers, complementing training time objectives.
Mickaël Basson, Philippe Preux
CRIStAL, Scool · Université de Lille, France · CNRS, France +2
The Traveling Salesperson Problem (TSP) is one of the best-known problems in computer science and arises in many engineering applications, such as smart vehicles and intelligent transportation systems. In the "Euclidean" case, each node is defined by its coordinates in the plane and distances are computed using the Euclidean metric. In the Constraint Programming (CP) literature, the Euclidean TSP is typically addressed by computing the full distance matrix and treating it as a general case; however this approach ignores the geometric information carried by the points' coordinates. In this work, we propose new filtering algorithms, implemented in Constraint Logic Programming (CLP), that exploit such geometric information to achieve stronger constraint propagation than existing approaches. Moreover, we show how this methodology can be extended to other Euclidean variants of the TSP, including the Euclidean Generalized Traveling Salesperson Problem (EGTSP), which is relevant in practical routing and logistics applications. Experimental results demonstrate the computational advantages of the proposed approach.
Alessandro Bertagnon, Marco Gavanelli
Department of Environmental and Prevention Sciences, University of Ferrara, Italy · Department of Engineering, University of Ferrara, Italy