PLMA: Un Nuovo Framework per Risolvere Problemi di Assegnazione Quadratica

arXiv:2604.20109 introduce PLMA, un framework di apprendimento delle permutazioni per il problema di assegnazione quadratica (QAP), un compito NP-hard fondamentale. PLMA presenta una procedura efficiente di messa a punto MCMC con inizializzazione a caldo che migliora le prestazioni in fase di deployment utilizzando brevi catene di Markov per ancorare l'adattamento a regioni promettenti. Per un'esplorazione rapida dello spazio delle permutazioni, impiega un modello energetico additivo (EBM) che consente il campionamento Metropolis-Hastings a 2 scambi in tempo O(1). La rete neurale che parametrizza l'EBM incorpora un meccanismo di attenzione cross-graph scalabile per modellare le interazioni tra le strutture. Questo lavoro affronta la sfida di ottenere prestazioni costantemente competitive su istanze QAP reali strutturalmente diverse, colmando il divario tra euristiche tradizionali e solutori basati sull'apprendimento.