User Datagram Protocol

Branch-and-Bound

Consideriamo il problema:

min

Sia x* la sua soluzione ottima di valore z* e x° la soluzione ottima del problema di PL ottenuto rilassando il vincolo di integralità di valore z°

Ovviamente    z°= c^Tx° z* = c^Tx*

Se anche x° è intero allora z° = z* e x* = x°

Altrimenti sia x°_i una componente frazionaria di x°. Possono darsi solo due casi (mutuamente esclusivi):

x*_i x°_i oppure x*_i x°_i

ovvero la componente i-esima del vettore ottimo x* sarà o al massimo uguale al massimo intero contenuto in x°_i  , oppure non minore del minimo intero contenente x°_i

BRANCH

Il problema originale dà origine a due problemi con regioni di ammissibilità ad intersezione nulla:

z' = min

z'' = min

e avremo z* = min .

Se rilassiamo il vincolo di integralità in questi due problemi e chiamiamo con x' ed x'' i due vettori di variabili ottimi, questi saranno in generale ancora non interi e si dovrà continuare a ramificare ("branch"). Ad ogni ramificazione si generano due nuovi problemi a meno che uno dei due non risulti intero oppure con regione di ammissibilità vuota (problema di PL inammissibile).

I vari problemi generati in questo modo possono memorizzarsi con una struttura dati costituita da un albero binario detto albero di decisione T.

BOUND

Consideriamo il k-esimo nodo dell'albero binario T e indichiamo con x^k e z^k rispettivamente il vettore ottimo e il valore della soluzione ottima del corrispondente problema di PL ottenuto rilassando il vincolo di integralità.

• z^k = c^Tx^k valore ottimo intero del problema corrispondente al k-esimo nodo di T = z*^k

• tutti i nodi di T discendenti del k-esimo avranno soluzioni z*^j z*^k z^k

• sia b il valore della soluzione intera migliore fra tutte quelle trovate in corrispondenza di nodi di T esplorati prima del k-esimo

• se z^k b, nessun nodo discendente dal k-esimo potrà fornire una soluzione di valore migliore e quindi il nodo k-esimo può essere chiuso ("fathomed")

IN GENERALE SI DEVE DECIDERE:

1. come scegliere il successivo nodo di T da esplorare, cioè da cui ramificare ("branching")

2. come generare i nodi "li" del nodo scelto

3. come calcolare le stime per difetto ("lower bounds") nel caso di un problema di minimo, o per eccesso ("upper bounds") per uno di massimo

Vediamo come si presenta un generico algoritmo di Branch-and-Bound

begin

activeset := ;

//0 nodo di T corrispondente al problema originale//

currentbest := Φ ; b :=

//currentbest memorizza il nodo corrispondente alla migliore soluzione disponibile e b il suo valore//

while activeset //insieme vuoto// do

begin

scegli un nodo k di activeset per ramificare ;

activeset := activeset ;

genera i li k_i di k , i=1,2,.,n_k e calcola i corrispondenti lower bounds zⁱ ;

for i := 1 to n_k do

if zⁱ b then chiudi il nodo k_i else

if k_i fornisce una soluzione completa^(§)

then b := zⁱ and currentbest := k_i

else activeset := activeset

end

end

(§) si preferisce parlare di soluzione "completa" invece che "intera" per offrire una versione più generica dell'algoritmo

Progetto e proprietà di un algoritmo di Branch-and-Bound

A)      Generazione dei li

binaria oppure multipla

con quale ordinamento delle variabili

B)       Strategia di esplorazione

Best-first

Depth-first

Altro

C)       Stime ("bounds")

tramite rilassamento del vincolo di integralità

con altri rilassamenti (Lagrangiani o surrogati)

D)      Inizializzazione: è spesso utile ottenere mediante un metodo euristico una soluzione ammissibile (subottima)

E)       Riduzione: prima di iniziare fissare più variabili possibile

F)       Arresto anticipato: possibilità di sovrastimare l'errore commesso

GUB BRANCH

Molti modelli contengono vincoli GUB (Generalized Upper Bounding) del tipo S_j=1,.,k x_j=1 con x_j binarie. Se la soluzione del rilassamento lineare ha alcune variabili x₁*,.,x_k* frazionarie, la regola di branch standard distingue i due casi x_j=0 e x_j=1 per un certo indice j. Tuttavia a causa del vincolo GUB il primo caso lascia aperte k-l possibilità, mentre il secondo caso ne permette solo una. Questo porta ad un albero decisionale di B&B sbilanciato.

"GUB branching" corregge questa caratteristica, specificando un ordine delle variabili (che può essere diverso da quello originario, ma che qui per semplicità di scrittura assumiamo sia uguale), e pone

S₁ = S

S₂ = S

dove r = min . In molti casi tale regola di branch riduce notevolmente il numero di nodi dell'albero decisionale.