Analisi Sperimentale del Costo Computazionale di Problemi su Grafi Formulati in Programmazione Lineare Intera

La programmazione lineare intera è uno strumento molto potente e versatile perché permette in poche righe di codice di scrivere programmi per risolvere problemi complessi, però tutta questa versatilità si paga con il tempo di esecuzione che nel caso pessimo può esplodere esponenzialmente. Inoltre dato un programma lineare non esiste una analisi tipo Big-O per classificarlo in una classe di complessità tempo e quindi il principale modo per valutare il costo computazionale di un programma lineare, oltre al misurare il numero di variabili e vincoli necessari, rimane quello di valutarlo sperimentalmente. Il lavoro di questa tesi consiste nel valutare sperimentalmente il costo computazionale impiegato per risolvere alcuni problemi su grafi utilizzando modelli in programmazione lineare intera. Sono stati considerati i seguenti problemi di ottimizzazione su grafi, tutti noti ammettere algoritmi polinomiali deterministici: cammini minimi fra una singola coppia, cammini minimi a sorgente singola, cammini minimi fra tutte le coppie e albero di copertura minimo. I modelli sono stati risolti con il risolutore glpsol, incluso nel package GLPK (GNU Linear Programming Kit) versione 5.0.