Algoritmo di branch & cut

[Cesidio Di Nicola]

Ciao a tutti,
sto risolvendo un problema di ottimizzazione combinatoria.
in particolare ho un problema di Programmazione lineare e sto cercando di
risolverlo tramite l'algoritmo di branch & cut.
Questo algoritmo a lezione (ottimizzazione 2) era stato applicato per
risolvere
un problema di max stable set. Il mio problema � un PL ad 8 variabili
diverso e sto
provando nel seguente modo (non sono sicuro se sto facendo la cosa giusta):
1. Tramite lindo risolvo il PL iniziale.
2. Faccio branch sulla variabile non intera della soluzione restituita
precedentemente
3. Ad esempio se utilizzo la strategia depth-first esploro l'albero partendo
da sinistra
4. Nel nuovo sottoproblema rafforzo la formulazione inserendo dei vincoli
cover
5. Inserisco il vincolo nel PL iniziale e calcolo l'ottimo in quel punto
6. faccio di nuovo branch sulla variabile non intera

Qualcuno di voi sa se sto procedendo nel modo corretto? Oppure avete qualche
link da girarmi su cui posso prendere spunto?

Grazie mille

Cesidio

[la.gekka]

solo un piccolo appunto tra il punto 4 e il punto 5. Alla cover
trovata devi applicare l'algoritmo di lifting per renderla valida in
ogni punto dell'albero. Inoltre dopo il cut puoi fare di nuovo cut
prima del branch. (<-- ok l'ho spiegato malissimo)

On 3 Giu, 20:02, "Cesidio Di Nicola" <cesidiodinic...@gmail.com>
wrote: