I miei principali interessi di ricerca ricoprono il settore della Ricerca Operativa e le sue applicazioni a problemi reali. In particolare l'attività si è rivolta ai seguenti argomenti, tutti classificabili nell'area della Programmazione Matematica Lineare, Intera, e Intera-Mista:
I progressi nella Programmazione Matematica Intera hanno permesso la soluzione di problemi di dimensioni impensabili appena alcuni anni fa. Per questo la ricerca sta affrontando ora nuove frontiere. La Programmazione Intera e la Programmazione Non Lineare sono state due settori che sono progrediti autonomamente con pochissime interazioni, sviluppando metodi diversi: metodi geometrici per la Programmazione Intera, metodi analitici per la Programmazione Non Lineare. Oggi, le conoscenze acquisite rendono possibile affrontare nuovi problemi che richiedono l'integrazione dei due settori per definire metodi risolutivi efficienti. Tali nuovi problemi contengono elementi di entrambi i settori e costituiscono la Pogrammazione Non Lineare Intera-Mista (MINLP), dove sono contemporaneamente presenti funzioni non lineari e vincoli di integralità su tutte o parte delle variabili.
Nell'attività di ricerca personalmente sviluppata sono stati considerati problemi in cui sono presenti variabili che devono assumere o il valore zero, oppure un valore compreso all'interno di un certo poliedro, pagando un costo fisso nel caso in cui il valore assunto non sia zero [FrG06a].
Tali variabili, chiamate semi-continue, sono presenti in modelli per molte applicazioni riguardanti per esempio problemi di produzione di energia elettrica, di ottimizzazione di portafoglio, di progettazione di reti di comunicazione e altri ancora.
Sono stati considerati problemi di Programmazione Non Lineare Intera-Mista con n variabili semi-continue xi.
È noto che la chiusura convessa della funzione obiettivo di tali problemi è connessa al concetto di perspective function la quale produce un rilassamento continuo significativamente piú forte rispetto alla funzione originale, e perciò costituisce un punto di partenza piú conveniente per sviluppare algoritmi di soluzione esatti o approssimati.
Usando quindi una caratterizzazione del subdifferenziale della perspective function è stata derivata una famiglia di disuguaglianze valide per il problema: i tagli prospettici. L'uso dei tagli prospettici migliora in modo sostanziale le performances di algoritmi enumerativi di tipo Branch-and-Cut. Nel lavoro [FrG07c]. l'approccio è stato ulteriormente migliorato per la classe di problemi che presenta una funzione obiettivo non separabile, quale il caso del problema di Mean-Variance per l'allocazione di portafoglio. Il metodo dei tagli prospettici è stato confrontato computazionalmente con una riformulazione alternativa, proposta in letteratura e basata su vincoli conici, risultando sempre la piú competitiva [FrG09]. I tagli prospettici sono stati impiegati nella risoluzione di problemi di gestione di centrali elettriche per ottenere migliori formulazioni di Programmazione Intera-Mista [FGL09], [FGL07].
Successivamente è stato ideato un metodo risolutivo alternativo
per i problemi con funzione obiettivo quadratica [FGGP09],
[FGL09b],
[FFGP10], applicabile solo sotto
opportune ipotesi riscontrabili, però, in molti problemi applicativi di questa
classe apparsi in letteratura. Esso è basato su un metodo di proiezione che
trasforma il rilassamento ottenuto con la formulazione prospettica
in un rilassamento con solo funzioni quadratiche convesse. Il metodo è stato
applicato ad un problema di progettazione di reti di telecomunicazioni e ad un
problema di posizionamento di radar risultando in entrambi i casi piú efficiente
di tutti i metodi precentemente proposti in letteratura, incluso quello dei
tagli prospettici. Esso risulta quindi il primo metodo basato su tecniche di
ottimizzazione non lineare a superare i metodi di linearizzazione.
Una diversa linea di ricerca ha invece trattato la soluzione di un particolare problema MINLP tramite un algoritmo di programmazione dinamica [FrG06b]. Il problema trattato sorge nella risoluzione di problemi di gestione di centrali elettriche risolti tramite rilassamento lagrangiano [FGL06], [FGL08]. Infine in [FGL07] è stato proposto un approccio ibrido che migliora su entrambi i metodi di partenza.
Uno dei più importanti problemi di ottimizzazione combinatorica è il problema del Massimo Insieme Stabile. Esso permette di modellare una molteplicità di problemi reali. Pur essendo uno dei problemi più studiati è ancora un problema che presenta moltissime domande irrisolte sia dal punto di vista computazionale che dal punto di vista teorico. Il problema è stato affrontato da due visioni algoritmiche completamente opposte, i metodi primali per problemi combinatori e i metodi poliedrali, ottenendo i risultati esposti di seguito.
Nel lavoro [GGV08a] è stata definita una nuova operazione di composizione di grafi chiamata gear composition, la quale produce un grafo G a partire da un dato grafo H e da un specifico grafo B chiamato gear. Questa operazione di composizione permette di costruire controesempi ad una congettura sulla struttura del poliedro STAB(G), l'inviluppo convesso di tutti gli insiemi stabili in G, nel caso in cui G sia un grafo claw-free e abbia numero di stabilità maggiore di 3. Il problema dell'insieme stabile sui grafi claw-free risulta essere una generalizzazione del piú noto problema di Matching.
L'attività di ricerca è proseguita con la determinazione di tutte le disuguaglianze che determinano facce massimali di STAB(G) a partire dalle disuguaglianze che definiscono il politopo associato ad H e a una suddivisione di H [GGV09]. Infine sono state studiate in [GGV09b] le relazioni di questa operazione di composizione con la strip decomposition di Chudnovsky-Seymour per i grafi claw-free, mostrando che essa costituisce una controparte poliedrale della loro decomposizione. In particolare è stata determinata una descrizione poliedrale per un ampia sottoclasse dei grafi claw-free [GGV09c].
Successivamente è stato determinato un risultato valido per ottenere la descrizione del poliedro dell'insieme stabile di grafi che sono composizione di grafi piú piccoli, introducendo la decomposizione 2-bond di un grafo [GGV09d] che generalizza altre decomposizioni presenti in letteratura quali la 2-join e la 2-amalgam.
Ciò costituisce un insieme di passi decisivi verso la soluzione del problema di determinare la descrizione di STAB(G) per grafi claw-free, il quale è un problema aperto dal 1981, quando fu dimostrato che l'insieme stabile su grafi claw-free è determinabile in tempo polinomiale.
I metodi del Punto Interno, oltre a risolvere i problemi di Programmazione Lineare in tempo polinomiale, risultano competitivi con i metodi del Simplesso anche in pratica. Allo stato attuale, però, non è stato fatto uno studio esaustivo sulla possibilità di sfruttare la struttura di uno specifico problema nella sua risoluzione tramite algoritmi del Punto Interno. Al contrario, per il metodo del Simplesso, esistono diverse varianti per la risoluzione dei problemi di flusso di costo minimo, o per problemi di flusso multicommodity di costo minimo. Al fine di studiare alcune specializzazioni dei metodi del Punto Interno ai problemi di flusso di costo minimo, in [FrG04], [FrG07a] proponiamo un nuovo insieme di precondizionatori per la risoluzione iterativa (approssimata), mediante il metodo dei Gradienti Coniugati con Precondizionamento (PCG), dei sistemi alle equazioni normali che è necessario risolvere ad ogni iterazione di un metodo del Punto Interno. Tali precondizionatori sono basati sull'idea di estrarre un sottografo del grafo originale che contiene, possibilmente in modo stretto, un albero di copertura. Definiamo una nuova classe di grafi, chiamata ``Brother-Connected Trees'' (BCT), con la proprietà che il precondizionatore associato può essere fattorizzato senza fill-in, e discutiamo alcune euristiche per determinare BCT di peso elevato. Gli esperimenti computazionali hanno dimostrato che i nuovi precondizionatori possono essere di complemento al precondizionatore ad albero (M. Resende e altri) e sono superiori ad essi sia nella riduzione del numero di iterazioni PCG che nella riduzione del tempo di esecuzione su alcune classi di grafi. In [FrG07b] è stato inoltre proposto un metodo che combina un algoritmo del punto interno con un algoritmo per i problemi di flusso di costo minimo.
Nel 1958 Gomory ha per la prima volta dimostrato che è possibile risolvere problemi di programmazione lineare intera attraverso piani di taglio. I tagli di Gomory sono poi stati sistematizzati in un lavoro di Chvàtal del 1973. Più recentemente Caprara e Fischetti hanno reinterpretato i tagli di Gomory come tagli modulo k, dove k è un numero intero (1996). Nel lavoro [GVW06] è stato dimostrato che l'inviluppo convesso di un insieme di punti interi ammissibile con vincoli di limiti inferiori e superiori si può descrivere attraverso l'uso dei soli tagli modulo 2. In generale, però, saranno necessari più iterazioni di generazione rispetto all'utilizzo di generici tagli di Gomory. La classe di problemi per cui si applica questo risultato è molto ampia e contiene, ad esempio, tutti i problemi con variabili 0-1 in cui sono compresi tutti i problemi più studiati (Stable Set, Set Covering, Traveling Salesman Problem, solo per citare tre casi).
Per questo argomento sono stati affrontati principalmente due
problematiche: la programmazione dei turni del personale e
la schedulazione di navi per il trasporto di prodotti petroliferi.
I problemi di programmazione dei turni del personale sono stati studiati in molti lavori in relazione a diversi settori applicativi. In generale tali problemi sono difficili sia per le simmetrie tra soluzioni ammissibili, che per gli elevati gap tra soluzione ottima intera e soluzione ottima del rilassamento continuo che tipicamente si presentano. In [BFFGP00] e [BFGP99] è stato esaminato il problema della formazione dei turni del personale di terra di un aeroporto. In [BFFGP00] vengono esposte tutte le fasi che portano dagli orari dei voli ai turni assegnati al personale; si distinguono 5 fasi differenti:
a) la pianificazione delle risorse, ovvero la determinazione del numero di persone necessario in ciascun giorno; b) la pianificazione dei roster, corrispondente alla produzione di una tabella di turni che ricoprono le necessità stabilite al punto precedente rispettando i vincoli contrattuali; c) il ``roster dressing'', attribuzione dei roster a persone fisiche; d) la gestione operativa dei turni, ovvero la ricopertura dei turni in caso di eventi imprevisti; e) l'assegnamento dei job al personale.
Dopo lo studio generale del problema della pianificazione delle
risorse a terra sono stati approfonditi i punti (b) e (d) proponendo
algoritmi risolutivi. Per la pianificazione dei roster (b) vengono
presentati due algoritmi il primo basato sulle tecniche poliedrali e
le regole di branching studiate in
mentre il secondo è
un'euristica basata su tecniche di scambio. La gestione operativa (d)
viene modellata attraverso un problema di flusso su un opportuno grafo
e quindi può essere risolta attraverso algoritmi efficienti per
problemi di flusso su reti. In
viene studiato il problema della
determinazione della soluzione ottima per la pianificazione dei roster
attraverso diverse classi di tagli. Dal punto di
vista teorico, alcune di esse hanno la proprietà di definire facce
massimali per uno specifico sottoproblema. Inoltre, viene descritta
una tecnica di risoluzione in due fasi: nella prima si applicano le
disuguaglianze valide studiate ad un sottoproblema che condivide con
il problema generale gran parte della struttura, ma contiene meno
variabili e vincoli. La risoluzione di tale sottoproblema permette
quindi di identificare un tipo di tagli che riduce fortemente il gap
nel problema completo. Unitamente alle altre classi di tagli il gap è
ridotto fino al 90%. Infine, vengono analizzate le simmetrie presenti
nel problema con l'obiettivo di impiegarle nella definizione di regole
di branching capaci di rompere tali simmetrie e ridurre l'ampiezza
dell'albero di enumerazione. I risultati di tale lavoro sono stati
inclusi nelle procedure aziendali di Alitalia e sono in uso per la
definizione dei turni del personale di terra dell'aeroporto di Roma
Fiumicino. Inoltre, il metodo sviluppato è stato presentato in due
conferenze sull'applicazione dei metodi della Ricerca Operativa a
problemi di compagnie aeree, ricevendo in entrambi i casi il premio
quale ``Best Technical Presentation'' [BFGP99].
Il problema della schedulazione di navi per la distribuzione di prodotti petroliferi è stato affrontato nei lavori [FGR98] e [Fetal03]. Un insime di beni sono prodotti e consumati in basi differenti in un certo orizzonte temporale. La distruzione avviene tramite una flotta di navi. È stato trattato in maggiore dettaglio il caso della distribuzione dei greggi per un'azienda petrolifera dalle basi di carico (vicino ai luoghi di estrazione) alle raffinerie presenti nel territorio nazionale. Il modello sviluppato è in uso nella società AgipPetroli S.p.A. (oggi divisione della società ENI S.p.A) per produrre il piano di distribuzione mensile e per gestire in modo ottimale le disfunsioni giornaliere che possono occorrere a livello operativo.
Molti problemi che sorgono nelle applicazioni reali si presentano con formulazioni a blocchi, caratterizzati da sottoinsiemi di vincoli definiti su sottoinsiemi disgiunti di variabili del problema. In generale tali problemi sono difficili sia per le elevate dimensioni, sia per la presenza di proprietà di simmetria. Nei lavori finora apparsi ogni specifico problema è stato affrontato separatamente sfruttando le sue particolari proprietà. In per la prima volta vengono studiate alcune proprietà poliedrali valide su ampie classi di problemi. In particolare, viene esaminata la proprietà di lifting con coefficienti zero delle disuguaglianze che definiscono facce massimali per i poliedri associati alle soluzioni dei singoli blocchi. Si verifica, quindi, che tale proprietà non è valida in generale. Tuttavia, sono state identificate classi di problemi (dove i vincoli che legano i blocchi sono del tipo bound generalizzato) per cui quelle disuguaglianze che inducono facce massimali per i singoli blocchi, inducono ancora facce massimali sul problema completo. Inoltre, sono state fornite delle condizioni affinché i bounds generalizzati definiscano anch'essi facce massimali. In [Ge00a] e [Ge00b] è stato anche studiato un caso particolare di problema a blocchi: il problema dei k Matchings Perfetti Disgiunti. Sono stati applicati a questo caso i risultati ottenuti per classi generali di problemi a blocchi discussi sopra. Inoltre, sono state puntualizzate le differenze tra il caso k = 1 e il caso k > 1. In particolare nel caso k > 1 il problema è NP-hard; inoltre, si presenta una differenza dal punto di vista poliedrale: mentre nel caso k = 1 il poliedro dei Matchings Perfetti si ottiene dal poliedro dei Matchings trasformando i vincoli di grado in vincoli di uguaglianza, nel caso k > 1 ciò non è sufficiente. Si distinguono quindi disuguaglianze che sono valide anche per il problema dei k Matchings Disgiunti e disuguaglianze che sono valide solo se si aggiunge la condizione di perfezione dei matchings. Per il primo tipo di disuguaglianze sono state sviluppate due tecniche di lifting applicabili a classi generali di tagli. Nel secondo caso sono state studiate alcune classi di disuguaglianze specifiche.
Nell'ambito dei problemi di Supply Chain Management sorge frequentemente la necessità di risolvere modelli di programmazione intera e mista di elevate dimensioni. Per risolvere efficientemente il rilassamento continuo di tali problemi si usano con successo metodi di decomposizione quali la tecnica di Dantzig-Wolfe. Negli anni novanta, inoltre, il Branch-and-Cut si è affermato tra i metodi per risolvere all'ottimo problemi a variabili intere. L'integrazione delle due tecniche sarebbe quindi utile per la risoluzione all'ottimo di questi problemi. Poiché tale integrazione comporta notevoli difficoltà sia teoriche che implementative, la sua realizzazione non è mai stata affrontata in precedenza nella letteratura. In [FGR00a] viene presentato un modello per i problemi di distribuzione all'interno di problematiche di Supply Chain Management considerando il livello della programmazione tattica. Nell'introduzione dell'articolo viene discussa la classificazione dei problemi di Supply Chain Management dal punto di vista delle fasi (acquisizione delle materie prime, produzione e distribuzione) e dal punto di vista dei livelli di pianificazione (strategico, tattico e operativo). In tale lavoro vengono, inoltre, presentate le caratteristiche base del problema e le possibili estensioni necessarie per ricoprire situazioni particolari che si verificano nella realtà. Sono proposti modelli di programmazione intera e di programmazione intera mista. Per la risoluzione del problema viene indicata una tecnica che combina i metodi Branch-and-Cut con la tecnica di decomposizione di Dantizig-Wolfe (Column Generation) basate sull'utilizzo di due formulazioni: la prima, denominata Subsets, è utilizzata per risolvere il rilassamento continuo tramite Column Generation, l'altra, denominata Block, viene utilizzata per identificare regole di branching e piani di taglio che vengono poi trasformati nei termini della formulazione Subsets. Per quanto riguarda lo studio poliedrale vengono indicate diverse classi di tagli studiate in parte per la programmazione intera e in parte per la programmazione intera mista. Le prime sono poi applicabili anche ai modelli di programmazione mista attraverso l'utilizzo di procedure di lifting di cui sono stati migliorati gli algoritmi risolutivi. Infine viene presentata un'applicazione alla distribuzione di prodotti petroliferi mediante navi in cui sono stati esaminati casi reali proposti da compagnie petrolifere. Questo lavoro è un'estensione dei lavori [Ge00a], [Ge00b] e [FGR00b] ed è stato in parte svolto nell'ambito del progetto HChLOUSO del programma ESPRIT finanziato dall'Unione Europea. Tra i partners del progetto vi sono due società che operano nel settore petrolifero (Agip Petroli e CLH - Spagna) che hanno fornito sia le specifiche che i casi test.
Gli ipergrafi orientati costituiscono un modello di struttura dati che
permette di rappresentare molti problemi sia teorici che applicativi
(problemi di soddisfacibilità, problemi di trasporto urbano,
progettazione di basi di dati relazionali, etc.). In particolare
l'applicazione degli ipergrafi orientati ai problemi di
soddisfacibilità (proposta per la prima volta da G. Gallo) ha permesso
di implementare in modo più efficiente algoritmi descritti in
precedenza da altri autori e di definire nuovi algoritmi, tra i
migliori oggi disponibili, presentati con successo alle competizioni
DIMACS. Seguendo tale filone di ricerca in
[GGPR98],
[Ge95] e [GGP95] è stata
studiata l'applicazione degli ipergrafi orientati ai problemi di
massima soddisfacibilità, ossia il problema di determinare il numero
massimo di clausole soddisfacibili all'interno di una formula non
soddisfacibile.
In particolare, nell'articolo
[GGPR98]
è stato
dimostrato che il problema di massima soddisfacibilità può essere
ricondotto ad un problema di taglio minimo su ipergrafi orientati. È
stata proposta una gerarchia di formulazioni nel caso di problemi con
formule logiche di tipo Horn. In tali formulazioni è presente un
numero superpolinomiale di vincoli. La prima formulazione rientra
nella classe dei problemi di programmazione disgiuntiva. Per essa è
stato dimostrato che il rilassamento continuo ammette sempre una
soluzione ottima intera. Inoltre, il problema della separazione dei
vincoli è risolvibile in tempo polinomiale. Tuttavia, la risoluzione
del rilassamento continuo è NP-hard, in quanto la formulazione
contiene vincoli non lineari (vincoli disgiuntivi, ovvero il massimo
di un insieme di funzioni lineari maggiore o uguale a uno). La
seconda formulazione è di tipo set covering. Essa è stata utilizzata
per il disegno di un algoritmo di tipo Branch-and-Cut per la
risoluzione del problema. L'algoritmo, pur utilizzando di base la
formulazione set covering, considera nel sottoproblema di separazione
dei vincoli, che è NP-hard, elementi derivanti dalla formulazione di
programmazione disgiuntiva. La terza formulazione proposta è una
variante della formulazione set covering in cui i coefficienti della
matrice dei vincoli assumono valori non negativi anche maggiori di 1. Per essa è
stato dimostrato che sia il rilassamento continuo, sia il problema
della separazione dei vincoli sono risolvibili in tempo
polinomiale. Inoltre, la formulazione del problema di massima
soddisfacibilità di clausole Horn presente in letteratura è
equivalente a tale nuova formulazione, e di conseguenza le
formulazioni set covering e di programmazione disgiuntiva discusse in
precedenza sono più forti della formulazione classica. Infine, è
stata esaminata una linearizzazione della formulazione di
programmazione disgiuntiva che risulta, però, essere più debole di
tutte le altre formulazioni. In [Ge95] è stata proposta una
generalizzazione dei risultati descritti in
[GGPR98]
al caso di formule
logiche generali. Dal punto di vista teorico sono stati dimostrati due
teoremi che generalizzano agli ipergrafi orientati i ben noti teoremi
di flusso massimo/taglio minimo e di cammino minimo/tensione massima.
Mentre nel caso dei grafi orientati tali teoremi sono riconducibili ad
una proprietà di dualità forte, negli ipergrafi orientati tali
relazioni corrispondono ad una proprietà di dualità debole. In questo
lavoro viene, inoltre, presentata la generalizzazione della
formulazione Set Covering descritta in
[GGPR98]
per il solo caso delle
formule Horn e vengono messe in evidenza le difficoltà teoriche
nell'estendere l'algoritmo proposto in
[GGPR98]
al caso generale. Infine,
in [GGP95] vengono presentati casi di problemi di massima soddisfacilibità
risolvibili in tempo poliniomiale.