Il prestigioso ICS Prize del 2014 attribuito a un team di matematici italiani e statunitensi per il loro contributo alla gestione delle simmetrie nei problemi di ottimizzazione con numeri interi.

Nella soluzione di problemi di ottimizzazione combinatoria la presenza di simmetria tra le soluzioni costituisce una notevole complicazione quando si vuole identificare la soluzione ottima: anche gli algoritmi di ottimizzazione più evoluti, basati su tecniche di enumerazione implicita, vengono spesso messi in ginocchio dalla presenza di molte soluzioni equivalenti e simmetriche, che li costringe ad esaminare lo spazio delle soluzioni con enormi strutture ad albero che diventano velocemente in trattabili anche nel caso di problemi con dimensioni moderate.

Per questo motivo lo studio di tecniche per la gestione delle simmetrie viene considerata una delle ultime frontiere della ottimizzazione matematica a numeri interi.

Un  importante passo in avanti è stato compiuto recentemente dagli esperti di Ricerca Operativa italiani Stefano Smriglio e Fabrizio Rossi  della Università dell’Aquila, insieme ai colleghi Jim Ostrowski (University of Tennessee) e Jeff Linderoth (University of Wisconsin). In diversi lavori recenti, i quattro “nemici della simmetria” hanno proposto dei metodi innovativi per modificare il problema originario tramite dei vincoli aggiuntivi che si integrano nella esplorazione dell’albero delle soluzioni del problema e  che riducono drasticamente il numero di soluzioni equivalenti e simmetriche che un algoritmo deve esaminare prima di poter decretare l’ottimalità di una soluzione.

Il metodo, battezzato “Orbital Branching”, è valso il prestigioso premio 2014 ICS Prize, conferito annualmente dalla  INFORMS Computing Society (ICS) per il miglior lavoro pubblicato nel campo della Ricerca Operativa e della Computer Science. Serve dire che INFORMS sta per Institute for Operations Research and the Management Sciences, ed è la più grande associazione mondiale di specialisti nel settore della Ricerca Operativa del Management.

Le motivazioni della commissione internazionale si dividono equamente tra la solidità e l’eleganza matematica del metodo ed il suo forte potenziale applicativo: nei loro lavori i vincitori del 2014 ICS Prize mostrano come l’orbital branching consente di risolvere problemi combinatori finora irrisolti e di velocizzare notevolmente i tempi di soluzione di molti problemi caratterizzati dalla presenza di simmetrie nella loro struttura.

C’è quindi da attendersi che a breve questo metodo vada ad arricchire le performance dei principali solver commerciali impiegati dalle aziende per gestire al meglio i molti problemi complessi modellati come problemi di ottimizzazione intera o mista, dopo aver arricchito anche i suoi autori con la simbolica cifra di 1000 euro associata al premio ma con la impagabile soddisfazione di aver fornito un contributo importante al loro settore di ricerca.

Per saperne di più:

• informs.org/Community/ICS/Prizes/ICS-Prize
• Ostrowski, J. Linderoth, F. Rossi, and S.  Smriglio , Orbital Branching, Mathematical Programming, 126:147-178, 2011.
• Ostrowski, J. Linderoth, F. Rossi, and S.  Smriglio, Constraint Orbital Branching, IPCO 2008: Lecture Notes in Computer Science, Vol. 5035, Springer, 225-239, 2008.
• Ostrowski, J. Linderoth, F. Rossi, and S.  Smriglio, Solving Large Steiner Triple Covering Problems, Operations Research Letters, 39:127-131, 2011.

[A cura di Giovanni Felici]