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.