Ottimizzazione combinatoria

Linee di ricerca: 
Combinatorica poliedrale 
Ottimizzazione su reti 
Data Mining e classificazione
Disegno di reti di telecomunicazione 
Ottimizzazione di portafogli
Biologia computazionale 
Apprendimento automatico 
Ottimizzazione robusta
Soddisfacibilità di formule logiche 
Scheduling e Job-shop Scheduling 
 
Membri: 
Renato Bruni, Antonio Sassano (leader). 
 
Dottorandi: 
Alessandra Reale. 
 
L’Ottimizzazione Combinatoria ricerca un insieme ottimo di scelte all’interno di una collezione, finita ma molto vasta, di insiemi di scelte. La Teoria dei Grafi, la Programmazione Intera e la Combinatorica poliedrale sono gli strumenti metodologici di base per questa area.
 
L’attività del gruppo di ottimizzazione combinatoria risale ai primi anni novanta ed è focalizzata sia sullo studio delle proprietà  poliedrali di particolari strutture combinatorie che sulla progettazione e uso di sofisticati algoritmi per la soluzione di problemi reali. Inizialmente la ricerca era principalmente orientata verso lo studio teorico dei poliedri dell’insieme stabile e del set covering. Contemporaneamente, come naturale estensione, si studiavano anche algoritmi per la soluzione di problemi di colorazione di grafi e di assegnamento di frequenze. Prendendo le mosse da quest’ultimo problema, il gruppo si è introdotto al più generale problema di disegno di reti wireless che ha rappresentato un tema particolarmente fertile negli anni seguenti. Infine, temi emergenti negli ultimi anni sono stati il machine learning sia supervisionato che non, la biologia computazionale, l'ottimizzazione di portafogli, il job-shop scheduling. 
 
Il gruppo è attualmente in collaborazione con: University of Maastricht, University of Oslo, Università di Roma Tor Vergata, Università dell’Aquila, Università di Lecce, Politecnico di Milano, Università del Sannio, Italian National Statistic Office (Istat), Texas Tech University, ZIB Berlin. Il gruppo ha partecipato a un grande numero di progetti nazionali e internazionali. 
 
L'autorevolezza scientifica acquisita nel campo dei metodi e algoritmi per il progetto ottimo di reti di trasmissione televisive e radiofoniche (broadcasting)  ha favorito lo stabilirsi di una stretta collaborazione con l'Autorità  per le Garanzie nelle Comunicazioni. Nell'ambito di tale collaborazione il gruppo ha dato un deciso contributo alla definizione dei piani nazionali TV e radio. 
 
Le competenze maturate nei campi di data mining e machine learning hanno portato a una ormai decennale collaborazione con l'Istituto Nazionale di Statistica (Istat) sui temi della ricostruzioni automatica di informazioni. Questa attività ha tra l'altro  prodotto nuove metodologie utilizzate per la correzione dei dati famiglie del Censimento della Popolazione Italiana 2001, dei dati del Censimento dell’Agricoltura Italiana 2010, dei dati del Censimento della Popolazione Italiana 2011.
 
Attività future del gruppo comprendono, oltre alla naturale estensione dei temi suddetti, anche lo studio di algoritmi di ottimizzazione per la previsione e la gestione di crisi finanziarie; algoritmi di tipo cammini aumentanti per il problema del massimo matching pesato; lo studio delle proprietà poliedrali delle matrici intervallo e delle matrici staircase; l'uso di tecniche di ottimizzazione per problemi di classificazione; lo studio di approcci totalmente combinatori al progetto di reti wireless.
 
Progetti: 
 
APICE - Algoritmi per la Pianificazione Integrata e Controllo di reti wireless Eterogenee, progetto MIUR n. 2878. Gennario 2008 - Aprile 2010 MIUR 
 
Metodi di ottimizzazione su larga scala nelle telecomunicazioni, progetto PRIN 2008, n. 2008LLYXFS. Marzo 2010 - Marzo 2012 MIUR 
 
Modelli Robusti di Ottimizzazione Lineare e Intera per Problemi di Data Mining, Progetto di Ricerca di Ateneo "Sapienza". Dicembre 2013 - Maggio 2015
 
Tecniche di Data Mining efficienti, robuste e basate sull’ottimizzazione per la risoluzione di problemi di Classificazione e Selezione di Investimenti, Progetto di Ricerca di Ateneo "Sapienza". Dicembre 2014 - Maggio 2016