Rilassamento di Dantzig

[galois23]

Salve a tutti,

avrei bisogno di qualche informazione circa il rilassamento di Dantzig inserito nel contesto del problema dello zaino, solo che ho fatto una ricerca su internet e non ho trovato un granché...
Qualcuno saprebbe aiutarmi, magari indicandomi qualche link sul quale trovare quello che cerco???

Grazie mille in anticipo!!

[hamming_burst]

Ciao,
il primo libro di programmazione matematica che avevo sotto mano indica: "il metodo di scomposizione di Dantzig-Wolfe". E' lo stesso a cui fai riferimento te?

[galois23]

Si, credo che sia questo...
In pratica devo risolvere il problema dello zaino mediante il Branch and Bound e risolvere ogni sottoproblema con Dantzig... solo che non ho ben presente cosa sia questo metodo di scomposizione o rilassamento... in realtà non so nemmeno se le due cose sono uguali o diverse...

[Deckard1]

No sono due cose diverse: il metodo di decomposizione di Dantzig e Wolfe è un metodo di "column generation" che permette di risolvere problemi che hanno una matrice dei vincoli con un numero esponenziale di colonne senza la necessità di enumerarle tutte. Il secondo invece consiste nell'utilizzare un algoritmo greedy per il rilassamento continuo (e ottenere quindi un upper bound) e dopo fare branch sull'oggetto che non sei riuscito ad inserire completamente nello zaino.
Mi sono spiegato da cani ma su internet dovresti trovare una spiegazione completa. È un algoritmo classico usato per introdurre la tecnica del branch & bound.