Affordable Access

Dispensa Algoritmo Branch-and-Bound

Authors
Publication Date
Keywords
  • Fondamenti Di Ricerca Operativa T-A (L-Z)
  • 28639
  • Ingegneria
  • 0021
  • Ingegneria Gestionale
  • 0925
  • 2012
  • 6

Abstract

FROLA_2009bis_rilass_euristici Algoritmi branch-and-bound • Algoritmi per problemi di ottimizzazione combinatoria di tipo NP-difficile: F = insieme soluzioni ammissibili (supposto finito): y ∈ F ; z(y): funzione obiettivo (da massimizzare); (z, F ) = problema di determinare la soluzione y∗ ∈ F tale che z(y∗) ≥ z(y) ∀y ∈ F • Algoritmi di tipo branch-and-bound: “ingredienti”: · albero decisionale; · strategie di esplorazione; · rilassamenti; · dominanze; · tecniche di riduzione; · algoritmi euristici. 1 Metodo branch-and-bound • P 0 = (z, F (P 0)) ( problema da risolvere); Z(P 0) = max{z(y) : y ∈ F (P 0)}. • Branch-and-bound: suddivisione di P 0 in n0 sottoproblemi P 1, P 2, . . . , P n0 tali da “rappresentare globalmente” P 0; ottenuta mediante suddivisione di F (P 0) in sottoinsiemi F (P 1), F (P 2), . . . , F (Pn0) tali che n0� k=1 F (Pk) = F (P 0) (Z(Pk) = max{z(y) : y ∈ F (Pk)} (k = 1, . . . , n0)) Si ottiene: Z(P 0) = max{Z(P 1), Z(P 2), . . . , Z(Pn0)}. • (risolvere P 0) ⇔ (risolvere Pk (k = 1, . . . , n0)) � 1) determinare la soluzione ottima di Pk, oppure 2) dimostrare che F (Pk) = ❤�, oppure 3) dimostrare che Z(Pk) ≤ Z (Z = valore della miglior soluzione ammissibile di P 0 ottenuta in precedenza). • Preferibilmente, F (P i) ∩ F (Pj) = ❤� ∀ P i, P j : i �= j (“partizione” di F (P 0) in n0 sottoinsiemi). • Suddivisione ripetuta per ogni sottoproblema non risolto. 2 Albero decisionale ✖✕ ✗✔ P 0 ✧✧✧✧✧✧✧✧✧✧ ✡ ✡ ✡ ✡ ✡✡ . . . ❜❜❜❜❜❜❜❜❜❜ ✖✕ ✗✔ P 1 . . . ✖✕ ✗✔ P 2 ✖✕ ✗✔ P n0 . . .✁ ✁ ✁ ✁ ✁✁ ❆ ❆ ❆ ❆ ❆❆ ✖✕ ✗✔ . . . ✖✕ ✗✔ . . . . . . foglie = sottoproblemi da risolvere. • Diverse strategie per la scelta del sottoproblema da affrontare. • Per ogni Pk, calcolo di un valore U(Pk) (upper bound) tale che U(Pk) ≥ Z(Pk) • ⇒ 3) se U(Pk) ≤ Z, Pk non viene considerato. • Per ottenere un upper bound di Pk = (z, F (Pk)): rilassamento di Pk: problema R(Pk) = (zr, Fr(Pk)) tale che: a) Fr(Pk) ⊇ F (Pk), b) zr(y) ≥ z(y) ∀y

There are no comments yet on this publication. Be the first to share your thoughts.