In questa ricerca ci si propone di studiare una classe di problemi di partizione connessa ottima di grafi in cui la funzione obiettivo è basata sul gap delle componenti, definito come la differenza tra il valore massimo e il valore minimo di pesi associati agli elementi di una componente.
Si tratta di problemi che nel caso generale sono difficili da risolvere (NP-hard) e si vuole sia indagare sulla complessità su grafi a albero, sia sperimentare la performance di alcune formulazioni di programmazione matematica a variabili 0-1 per i problemi su grafi arbitrari.
Si intende inoltre studiare nuovi metodi di soluzione per il problema della bipartizione di un grafo con più criteri, utilizzando un approccio di programmazione matematica basato sulla formulazione del problema del taglio minimo di una rete e in grado di fornire soluzioni Pareto ottime o con tecniche di scalarizzazione o con nuovi algoritmi specifici.
Per i problemi basati sul gap, le formulazioni che si vogliono sperimentare dovranno includere dispositivi per l'eliminazione di simmetrie, la cui presenza rallenta la ricerca di una soluzione ottima negli algoritmi basati su una enumerazione parziale delle soluzioni. Inoltre si studieranno specifiche disuguaglianze valide, basate sul tipo di funzione obiettivo che potrebbero permettere di risolvere all'ottimo problemi di dimensioni maggiori rispetto a altri problemi di partizione connessa di grafi. Infatti, come già detto, le funzioni obiettivo basate sul gap hanno delle caratteristiche che permettono di ridurre il numero di variabili e eliminare le simmetrie.
Numerosi problemi di partizione connessa di grafi sono risolvibili in tempo polinomiale su grafi a albero. Inoltre, per alcune classi particolari di grafi a albero sono già conosciuti algoritmi efficienti di soluzione. Nella presente ricerca si vuole verificare l'esistenza di algoritmi polinomiali su grafi a albero arbitrari per le funzioni obiettivo basate sul gap, oppure dimostrare che si tratta di problemi NP-hard.
La ricerca affronta anche un problema che ricorre in molte applicazioni pratiche, ma che non è quasi mai affrontato come un problema di ottimizzazione multicriterio e quindi cercando di nascondere la complessità del problema nella stima più o meno sofisticata di un'unica funzione di costo. Tuttavia, questo approccio rivela i suoi limiti quando i dati di partenza sono relativi ad una realtà più articolata, come nel caso delle preferenze o opinioni di consumatori o cittadini ed è la causa della poca robustezza di alcuni sistemi con cui interagiamo ogni giorno, dalla pubblicità in rete ai sistemi di raccomandazione adottati da Netflix o Spotify.
In questo ambito il tema di questa parte del progetto si propone un approccio nuovo, evitando di comprimere l'analisi di una realtà complessa in un'unica soluzione, ma permettendo ad un decisore o ad un agente di valutare un insieme di soluzioni Pareto ottime. Il contributo metodologico della ricerca si inserirebbe in un filone in cui per ora sono presenti relativamente pochi lavori scientifici e pertanto avrebbe tutte le potenzialità per acquisire una buona rilevanza con la diffusione di queste tecniche negli ambiti citati.