sto lavorando ad una tesina che devo presentare per un esame (Ottimizzazione Combinatoria) in cui bisogna risolvere un problema di Simple Plant Location Problem (per chi non sapesse di cosa sto parlando, guardare spoiler) con 100 customers e 100 Plant Facility Location.
Testo nascosto, fai click qui per vederlo
There are a number of m cities/customers and n potential facility locations. With each location we associate a nonnegative opening cost f_i. Between each facility i and each city j there is a nonnegative connection or service cost c_ij. The task is to connect each city to exactly one opened facility the way that the sum of all costs is minimized.
Innanzitutto ho sviluppato l'algoritmo del Simplesso Dinamico nel linguaggio AMPL (http://it.wikipedia.org/wiki/AMPL) che avrebbe risolto il problema molto facilmente, se non fosse che per la student edition il massimo numero di variabili possibili è 300, il problema ne ha 10100 (100*100 + altre 100 che rappresentano l'attivazione, o meno, dell'impianto i-esimo).
Allora ho pensato di usare il Greedy Algorithm, l'ho implementato in Java e mi dà effettivamente una soluzione. La mia paura però è che non sia quella ottima (o addirittura sia molto lontana da essa) visto che l'algoritmo in questione non garantisce minimamente la "bontà" della soluzione trovata.
Quindi ho deciso di trovare qualche Lower Bound (Minorante) che possa "certificare" la qualità della mia soluzione (ovviamente più il gap tra il Lower Bound e la soluzione trovata è minore, più possibilità ha di essere la soluzione ottima o almeno buona).
Il problema è che non riesco a trovare nessun rilassamento lineare del problema di partenza di cui posso trovare il minimo col simplesso dinamico.
Qualcuno sa darmi una dritta?
Grazie in anticipo
