Progettare algoritmi migliori mettendoli in crisi con problemi difficili

ab8dfb219dbf23f9636bdc1903bab7bf.jpg

Servizio comunicazione istituzionale

19 Dicembre 2022

Un nuovo progetto di ricerca condotto da Luca Gambardella, professore dell’Istituto Dalle Molle di studi sull’intelligenza artificiale IDSIA (USI-SUPSI) e Prorettore all'innovazione e relazioni aziendali, è stato approvato dal Fondo nazionale svizzero per la ricerca scientifica (FNS). Lo studio intitolato “Computational methods for integrality gaps analysis” affronta da una prospettiva innovativa e originale l’ottimizzazione degli algoritmi per trattare problemi complessi.

Il progetto, della durata prevista di 4 anni, con un ricercatore postdoc e due dottorandi, è condotto in collaborazione con il professor Monaldo Mastrolilli della SUPSI, anche lui membro dell’IDSIA (USI-SUPSI). La ricerca si ispira ai recenti progressi degli algoritmi che combinano tecniche di intelligenza artificiale e metodi approssimati/esatti. Ma, invece di studiare gli algoritmi, cambia la prospettiva perché mira a metterli in crisi generando in maniera sistematica e matematicamente robusta istanze difficili da risolvere.

 

Professor Gambardella, che cosa si intende con problemi complessi?

La “teoria della complessità”, secondo la definizione di Oxford Languages, studia i sistemi formati da un grandissimo numero di elementi che interagiscono tramite regole definite e che sono soggetti a determinati vincoli. Lo scopo è comprendere i comportamenti globali e predire l'evoluzione di questi sistemi. In matematica, si cerca di determinare il numero minimo di operazioni necessarie per risolvere simili problemi. Un tema di ricerca in questo settore riguarda la misura della complessità di un problema valutandola, appunto, in base al numero di operazioni necessarie a risolverne una istanza rispetto al numero di dati di ingresso.

Numero di operazioni che immagino possa essere molto elevato.

Ci sono problemi “facili”, cioè risolvibili con un numero di operazioni che crescono in maniera polinomiale rispetto al numero di ingressi, e problemi “difficili” di cui parleremo successivamente. Un esempio di problema “facile” è il calcolo del percorso più corto tra due punti in un grafo pesato, pensiamo ad esempio all’itinerario di Google Maps. Sfortunatamente, esistono problemi “difficili” per i quali non si conosce un algoritmo polinomiale di risoluzione e c’è persino il dubbio che un tale algoritmo possa esistere. Risolvere questi problemi richiede l’utilizzo di algoritmi con un numero di operazioni che cresce con una complessità esponenziale rispetto ai dati di ingresso.

 

Può fare un esempio di problema “difficile”?

Invece di trovare il percorso tra due punti su una mappa, pensiamo al calcolo del percorso più breve che parte da una determinata città, visita un certo numero di città date e ritorna nella città iniziale. È un caso noto come “problema del commesso viaggiatore” e per risolverlo bisogna enumerare tutti i possibili percorsi e misurarne la lunghezza. Questo richiede il calcolo di un numero fattoriale di percorsi portando a una complessità esponenziale dell’algoritmo (in base all'approssimazione di Stirling). Purtroppo quando il numero di città cresce oltre le poche centinaia questi metodi esatti diventano impraticabili e dobbiamo ricorrere a metodologie che non garantiscono più di ottenere il percorso più corto ma che lo approssimano.

 

Come si affrontano questi problemi?

La strategia tradizionale per capire se questi algoritmi esatti o approssimati funzionano in pratica è di prendere un insieme di istanze del problema in esame e di testarle su un computer. Si studiano il tempo di calcolo effettivo per trovare una soluzione e la qualità delle soluzioni al crescere della dimensione del problema e al cambio della sua struttura. In parallelo si studia, a livello teorico, quale sia il rapporto massimo tra la qualità della soluzione di un programma lineare intero che risolve il problema e il suo rilassamento (integrality gap).

Per finalizzare questi studi in letteratura esistono librerie di riferimento che contengono istante di problemi di diversa natura sui quali i ricercatori si confrontano e talvolta si sfidano.

La nostra ricerca invece si basa su un altro approccio, la generazione sistematica e matematicamente robusta di istanze difficili da risolvere con l’obiettivo di capire i limiti degli algoritmi esistenti per poterne progettare di migliori.

 

Facoltà

Rubriche