Ricerca Lower Bound Problema PL01
Ciao a tutti,
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.
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
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.
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
Risposte
Premetto che non l'ho mai usato e che ho solo fatto una ricerca online, ma potresti forse usare GLPK che sembra essere un'alternativa open-sorce a AMPL. Sembra in effetti supportare un linguaggio di scripting simile ad AMPL e non dovrebbe avere limitazioni sul numero di variabili.
Il problema è che il professore ci ha espressamente detto che dandoci un problema non risolvibile "direttamente" (a causa del numero elevato di variabili) dovevamo ingegnarci per trovare una soluzione in qualche altro modo..
Io ci ho provato e ci sto provando ma non riesco proprio a capire come prendere questo rilassamento lineare, indispensabile per avere un Lower Bound..
Io ci ho provato e ci sto provando ma non riesco proprio a capire come prendere questo rilassamento lineare, indispensabile per avere un Lower Bound..
Potresti usare una tecnica di column generation.
Il metodo è molto simile a quello che hai implementato tramite simplesso dinamico, solo che in questo caso si parte da un numero ridotto di colonne e l'oracolo di separazione fornisce ad ogni iterazione una nuova colonna da aggiungere alla formulazione rilassata del problema. Cerca meglio sul web che è pieno di esempi.
Il metodo è molto simile a quello che hai implementato tramite simplesso dinamico, solo che in questo caso si parte da un numero ridotto di colonne e l'oracolo di separazione fornisce ad ogni iterazione una nuova colonna da aggiungere alla formulazione rilassata del problema. Cerca meglio sul web che è pieno di esempi.
Non conosco questo problema, ma vedendo la tipologia non capisco perchè parli di trovare la soluzione ottima.
L'ottimo non sai dove è, ne quando e se mai lo troverai attraverso il tuo algoritmo, proprio perchè è un problema "difficile".
Forse ne parli perchè utilizzi il simplesso che trova l'ottimo se esiste soluzione ammissibile (almeno nel simplesso reale lineare)...
L'ottimo non sai dove è, ne quando e se mai lo troverai attraverso il tuo algoritmo, proprio perchè è un problema "difficile".
Forse ne parli perchè utilizzi il simplesso che trova l'ottimo se esiste soluzione ammissibile (almeno nel simplesso reale lineare)...
"hamming_burst":
Non conosco questo problema, ma vedendo la tipologia non capisco perchè parli di trovare la soluzione ottima.
L'ottimo non sai dove è, ne quando e se mai lo troverai attraverso il tuo algoritmo, proprio perchè è un problema "difficile".
Appunto perchè la soluzione ottima non posso trovarla mi piacerebbe trovare un lower bound e confrontarlo con la soluzione che ho trovato per vedere quanto è grande il "gap" il problema è che non trovo nessun rilassamento lineare che posso risolvere facilmente..
Al massimo cerchi un upper bound. Il lower bound è dato dalla soluzione euristica. Comunque il metodo di column generation che ti ho suggerito prima dovrebbe essere ciò che fa per te, prova a dargli un'occhiata.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo