Metraipolis › archive › dc_2028c8fb7975

EDISCO: Equivariant DIScrete Diffusion for Euclidean Combinatorial Optimization — arXiv:2610.04953

Source
arXiv
Original
https://arxiv.org/abs/2610.04953
License (as archived)
CC0-1.0
Archived
2026-10-06T05:26:35.904Z
SHA-256 of the archived text
c1dfced3e2749a0382135538af79fa5a9581fcc2473e7cbdfc3b438890136749
Stable URL of this page
https://metraipolis.com/documento/dc_2028c8fb7975

How to cite

EDISCO: Equivariant DIScrete Diffusion for Euclidean Combinatorial Optimization — arXiv:2610.04953 — arXiv, https://arxiv.org/abs/2610.04953 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_2028c8fb7975 (Metraipolis archive dc_2028c8fb7975, sha256 c1dfced3e2749a0382135538af79fa5a9581fcc2473e7cbdfc3b438890136749)
BibTeX
@misc{dc2028c8fb7975,
  title = {EDISCO: Equivariant DIScrete Diffusion for Euclidean Combinatorial Optimization — arXiv:2610.04953},
  howpublished = {arXiv},
  url = {https://arxiv.org/abs/2610.04953},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_2028c8fb7975; sha256 c1dfced3e2749a0382135538af79fa5a9581fcc2473e7cbdfc3b438890136749},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv, https://arxiv.org/abs/2610.04953. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 this https URL .

Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.AI, nuovi lavori del giorno).
Categorie arXiv: Machine Learning (cs.LG) ; Artificial Intelligence (cs.AI).
Pagina del lavoro: https://arxiv.org/abs/2610.04953 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-06T05:24:05.949Z dalla pagina https://arxiv.org/list/cs.AI/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).