Problemi Inversi di Cammino Minimo

In questa tesi vengono affrontati due classici problemi di ottimizzazione inversa: l'Inverse Shortest Path Problem (ISPP) e l'Inverse Shortest Path Length Problem (ISPL). Dopo alcuni richiami al contesto del problema, cioè la teoria dei grafi, segue una breve analisi al problema del cammino minimo, da cui i problemi discendono. L'introduzione termina introducendo il concetto di ottimizzazione inversa, motivandone l'importanza. Si osserverà come in scenari reali caratterizzati da dati incerti o parziali la programmazione inversa risulti indispensabile per descrivere in maniera più veritiera modelli reali. Il primo dei problemi che verrà studiato è l'Inverse Shortest Path Problem (ISPP). L'obiettivo del problema, dato un grafo orientato, è di calcolare un vettore di costi per gli archi che renda minimi i cammini prescritti. Per questo problema si descriverà un algoritmo basato sul metodo duale di Goldfarb-Idnani. Dopo aver presentato questo algoritmo e aver descritto le modifiche necessarie l'algoritmo sarà quindi in grado di modificare in maniera minima i costi della rete per rendere ottimale il cammino prescritto. L'Inverse Shortest Path Length Problem, invece, prevede la ricerca di un vettore dei costi che renda i valori predefiniti le lunghezze dei cammini minimi tra alcune coppie di archi scelti. Per l'ISPL è, quindi, richiesto un approccio differente. Prima di tutto verranno presentate diverse formulazioni e casi particolari del problema. L'analisi della loro risoluzione ha origine da un algoritmo euristico. Verranno poi discussi due diversi approcci risolutivi, per individuare un insieme di costi che renda ottimo il valore obiettivo desiderato. L'analisi, non si limiterà a formalizzare i problemi e le relative varianti, ma metterà anche in evidenza casi in cui è possibile ottenere soluzioni in tempo polinomiale. Per questo secondo tipo di problema, più complesso del primo, sarà infatti importante anche una breve analisi sulla complessità.