EDISCO: diffusione discreta equivariante per l’ottimizzazione combinatoria euclidea

Abstract degli autori

I problemi di ottimizzazione combinatoria euclidea (ECOP), come il problema del commesso viaggiatore (TSP) e il problema di instradamento dei veicoli con vincoli di capacità (CVRP), presentano simmetrie intrinseche rispetto al gruppo euclideo bidimensionale E(2), tra cui rotazioni, riflessioni e traslazioni. I metodi esistenti basati sull’apprendimento, compresi quelli recenti basati sulla diffusione, ricorrono all’aumento dei dati o alla regolarizzazione per approssimare l’equivarianza rispetto a E(2). Questo articolo presenta EDISCO, il primo modello di diffusione discreta per gli ECOP con distribuzioni generative esattamente invarianti rispetto a E(2) sulle soluzioni espresse come indici dei nodi. EDISCO introduce una rete equivariante rispetto a E(2) che assegna punteggi agli archi, abbinata a una catena di Markov categoriale a tempo continuo su variabili discrete degli archi; il campionamento esatto dalla distribuzione a posteriori consente un’inferenza efficiente in più passaggi. Questa architettura conferisce a EDISCO un bias induttivo geometrico locale: gli intorni degli archi con la stessa geometria relativa e lo stesso contesto combinatorio vengono rappresentati in modo coerente, indipendentemente dalla posizione o dall’orientamento assoluti. Ciò rende l’apprendimento più efficiente e l’inferenza più robusta rispetto ai metodi non equivarianti. EDISCO supera i precedenti risolutori basati sull’apprendimento allo stato dell’arte su istanze sintetiche del TSP da 100 a 10.000 nodi e del CVRP da 50 a 2000 clienti, utilizzando soltanto il 33-50% delle istanze di addestramento. Pur essendo stato addestrato solo su dati sintetici distribuiti uniformemente, EDISCO supera anche i metodi di riferimento concorrenti basati sull’apprendimento quando cambia la distribuzione spaziale o il grado di rigidità dei vincoli del CVRP. Il codice è disponibile all’indirizzo https://github.com/ValleyC/EDISCO.