CaR: Un Nuovo Approccio per la Gestione dei Vincoli nei Solutori Neurali

I solutori neurali hanno dimostrato notevoli progressi nell'affrontare problemi di routing semplici, eccellendo in particolare nell'efficienza computazionale. Tuttavia, la loro efficacia in presenza di vincoli complessi è ancora limitata. Le attuali tecniche di gestione dei vincoli, come il mascheramento della fattibilità o la consapevolezza implicita della fattibilità, possono risultare inefficienti o inapplicabili per vincoli stringenti.

Per affrontare queste sfide, è stato presentato Construct-and-Refine (CaR), il primo framework generale ed efficiente per la gestione dei vincoli nei solutori neurali di routing, basato sul raffinamento esplicito della fattibilità tramite apprendimento automatico. A differenza degli ibridi costruzione-ricerca esistenti, che mirano a ridurre i gap di ottimalità attraverso miglioramenti intensivi ma faticano con vincoli stringenti, CaR raggiunge una gestione efficiente dei vincoli progettando un framework di training congiunto. Questo framework guida il modulo di costruzione a generare soluzioni diversificate e di alta qualità, adatte a un processo di miglioramento leggero.

CaR introduce anche il primo utilizzo di una rappresentazione condivisa tra costruzione e miglioramento, consentendo la potenziale condivisione di conoscenza tra paradigmi unificando l'encoder, specialmente in scenari vincolati più complessi. Le valutazioni su vincoli di routing tipici dimostrano che CaR raggiunge una fattibilità, una qualità della soluzione e un'efficienza superiori rispetto ai solutori classici e neurali all'avanguardia.