Research | Projects

SPANNING TREE GENERALIZZATI ED ALTRE VARIANTI

Il problema del “Minimum Spanning Tree con Coppie di Archi in Conflitto” è una variante del classico problema (P1) del Minimun Spanning Tree. Dato un grafo non orientato e pesato sugli archi G (V, E, P), dove P è un insieme di coppie di archi in conflitto, il problema consiste nel trovare un albero di copertura di peso minimo di G senza coppie di archi in conflitto. Piuttosto che definire il problema inammissibile se, per il grafo in esame, non esiste nessun albero ricoprente senza archi in conflitto, noi proporremo la seguente modifica del problema (problema P2): Dato un grafo non orientato e pesato sugli archi G (V, E, P) , dove P è un insieme di coppie di archi in conflitto, il problema consiste nel trovare un albero di copertura di peso minimo di G con il minimo numero di coppie di archi in conflitto. In questo caso è evidente che una soluzione ottima di P1 è sempre una soluzione ottima di P2 mentre il viceversa e' vero se e soltanto se l'ottimo di P2 è un albero ricoprente senza coppie di archi in conflitto. Per risolvere tale problema, abbiamo intenzione di sviluppare un algoritmo genetico basato sula definizione di cromosomi (soluzioni ammissibili) che rappresentano alberi ricoprenti del grafo iniziale e con una funzione di fitness in grado di gestire efficacemente prima la riduzione dei conflitti poi la riduzione del peso totale della soluzione. Inoltre proporremo un modello matematico e identificheremo classi di disuguaglianze valide al fine di definire un algoritmo esatto di tipo branch and cut. Il problema del minimo albero ricoprente generalizzato, nella sua versione generale, è così definito: dato un grafo G(V,E) ed una partizione dell'insieme dei nodi V in K clusters, occorre individuare un MST che contenga esattamente un vertice per ciascun cluster. Esistono diverse versioni del problema del minimo albero ricoprente generalizzato: 1) Versione Exactly (definizione precedente); 2) versione "at least": occorre individuare un MST checontenga almeno un vertice per ciascun cluster; 3) versione "at most" occorre individuare un MST che contenga al più un vertice per ciascun cluster. Relativamente a tale problema proporremo un algoritmo di tipo Branch and Cut per la risoluzione nella versione exactly e per la versione "at least". In particolare verificheremo la possibilità di rappresentare alcune versioni del problema tramite un modello matematico per il problema del minimo albero ricoprente nella versione Steiner e verificheremo l'efficienza di tale modello rispetto ai modelli ad hoc presenti in letteratura. Infine per ognuna delle tre versioni verranno proposti modelli matematici, approcci metaeuristici, math-euristici ed esatti.