SAG-Sep: grafi sparsi arricchiti e ricerca guidata da una struttura a cipolla per la separazione dei tagli di capacità arrotondati

Abstract degli autori

I tagli di capacità arrotondati (RCC) sono tra i tagli più efficaci per i rilassamenti del problema di instradamento dei veicoli con capacità, ma la loro separazione esatta è computazionalmente proibitiva su larga scala. I separatori euristici e neurali esistenti possono essere veloci, ma spesso non riescono a generare un numero sufficiente di tagli efficaci entro i budget di separazione pratici. Presentiamo SAG-Sep, un separatore che, a partire da una soluzione frazionaria del PL, assegna in un’unica passata forward dell’encoder un punteggio all’appartenenza dei nodi ai sottoinsiemi che generano RCC, per diversi livelli del numero di veicoli; in questo modo evita l’inferenza iterativa di previsione e coarsening usata dai separatori in stile NeuralSEP. SAG-Sep codifica la soluzione del PL come un grafo sparso arricchito (SAG), aggiungendo archi multi-hop informati dal flusso che rendono visibile la struttura di instradamento a lungo raggio senza rendere più densa l’attenzione. Oltre a questa codifica sparsa che tiene conto del PL, osserviamo che gli RCC esatti di alto valore sono in genere annidati e si organizzano in famiglie di sottoinsiemi a cipolla; i punteggi dei nodi di SAG-Sep rispecchiano la profondità di annidamento dei sottoinsiemi. Da questa osservazione nasce Onion-Sweep (OS), un decodificatore che non richiede addestramento: ordina i clienti in base ai loro punteggi, calcola in un’unica passata vettorializzata il grado di violazione delle RCC per ogni prefisso dell’ordinamento e restituisce il prefisso con la violazione maggiore di ciascuna replica, insieme a una famiglia di proposte annidate tra le repliche. In questo modo trasforma punteggi indipendenti dei nodi in candidati RCC coordinati strutturalmente, senza soglie calibrate né fasce di esplorazione. Sul benchmark NeuralSEP, con istanze da N=1000 clienti, SAG-Sep con OS riduce il gap medio alla radice del 17,7% rispetto al baseline NeuralSEP più competitivo, mentre il separatore SAG-Sep a passata singola accelera di circa 30 volte la separazione neurale per iterazione. I nostri risultati suggeriscono che la codifica sparsa che tiene conto del PL e la struttura annidata dei tagli di alto valore siano schemi strutturali che vale la pena sfruttare più ampiamente nella separazione neurale.