Nuovo algoritmo per risolvere difficili problemi di ottimizzazione
Nature Communications pubblica il lavoro di Giorgio Parisi e Federico Ricci-Tersenghi, che insieme a Raffaele Marino (KTH, Stoccolma) hanno sviluppato un nuovo algoritmo numerico per la risoluzione di difficili problemi di ottimizzazione combinatoria discreta.
Questi problemi compaiono in molte discipline scientifiche e campi di applicazione pratica, qualora si tenti di trovare la configurazione ottimale di un grande numero di variabili che soddisfino contemporaneamente un numero enorme di vincoli. Tra gli esempi di problemi che possono essere scritti in questi termini troviamo, ad esempio, il problema della fattorizzazione di grandi numeri interi, centrale nella moderna crittografia, e il problema del design e della verifica dei circuiti integrati.
Nei problemi di ottimizzazione combinatoria discreta, quando il numero dei vincoli per variabile diventa molto grande e si avvicina ad una soglia critica, oltre la quale le soluzioni al problema cessano di esistere, la ricerca delle poche soluzioni valide diventa un compito estremamente complesso e forse impossibile da risolvere in tempi che crescono solo con una potenza della dimensione del problema.
L’algoritmo proposto in questo lavoro (dal nome backtracking survey propagation) assegna le variabili del problema un po’ alla volta sulla base delle informazioni raccolte da una procedura di message passing che permette di stimare, per ogni variabile, il livello di confidenza con cui tale variabile potrebbe assumere uno dei suoi valori permessi.
In aggiunta, il nuovo algoritmo permette anche di liberare alcune variabili già assegnate, qualora il livello di confidenza del valore a cui sono state assegnate diventi troppo basso, a causa dell’assegnazione di altre variabili. Questa fase di backtracking è estremamente utile al fine di aggiustare errori commessi nella prima parte dell’assegnazione, permettendo così al nuovo algoritmo di risolvere problemi di ottimizzazione con decine di milioni di vincoli, molto vicino alla soglia critica.
Riferimenti bibliografici:
“The backtracking survey propagation algorithm for solving random K-SAT problems”, Raffaele Marino, Giorgio Parisi e Federico Ricci-Tersenghi, Nat. Commun. 7, 12996 (2016) doi: 10.1038/ncomms12996