Metodo branch and bound

Il metodo branch and bound, introdotto agli inizi degli anni '60, è uno dei metodi più diffusi per la soluzione dei problemi di ottimizzazione  discreta, qualora l'insieme delle soluzioni ammissibili sia limitato .

L'algoritmo BRANCH AND BOUND ( ossia  RAMIFICARE-dividere- e LIMITARE)  è una strategia di esplorazione dello spazio delle soluzioni ammissibili e si basa sui concetti di rilassamento, separazione, eliminazione.

 Rilassamento

Un problema P' si dice rilassamento di un problema P se l'insieme delle soluzioni ammissibili di P sono contenute in quello di P'

 Separazione

Un problema P si dice separato nei sottoproblemi P₁,P₂....P_n se:

•  l'unione degli insiemi delle soluzioni ammissibili relativi a tali sottoproblemi  è pari alla regione ammissibile del problema originale P;

• tutti i sottoproblemi condividono la  stessa f.o.

 La separazione si effettua considerando una variabile alla volta e separando P a secondo dei valori interi ammissibili di quella variabile in due sottoproblemi.

 Eliminazione

Un problema P si dice eliminato se un suo rilassamento P'   

• non ammette soluzioni

• il valore ottimo della f.o. è minore (maggiore) di quello corrente

 Il metodo branch and bound, quindi, consiste:

• nel generare una partizione ricorsiva della regione delle soluzioni ammissibili in sottoregioni disgiunte ( fase di branching -ramificazione-) ;

• nel determinare per ogni  sottoproblema una funzione UPPER BOUND detta CBUB (LOWER BOUND detta CBLB ) , ossia una limitazione superiore (inferiore) al valore che la soluzione ottima relativa al problema di P.L.I. potrà assumere (fase di bounding -limitazione-) Se la stima e` minore (maggiore) della migliore soluzione trovata, quel ramo viene tagliato (pruned). 

L' algoritmo si compone di cinque fasi:

1. Inizializzazione:si risolve il problema del rilassamento di programmazione lineare P.L. associato a quello di P.L.I.

2. Arresto dell'iterazione:

• se la soluzione ottimale del problema del rilassamento di P.L. è intera

    3. Rilassamento:si sceglie il sottoproblema della lista e si risolve il suo rilassamento continuo.

    4.FATHOMING:

•  la regione ammissibile del sottoproblema  è vuota(vai al punto 2);

•  l'ottimo  del sottoproblema ha un valore minore a quello della migliore soluzione nota,CBUB<CBLB (vai al punto 2).

•  l'ottimo  del sottoproblema è maggiore di quello della migliore soluzione nota ed ha   coordinate intere (vai al punto 2)

•  in un nodo risulta CBUB=CBLB (vai al punto 2)

•  l'ottimo  del sottoproblema è maggiore di quello della soluzione nota e non ha coordinate intere (vai al punto 5)

    5.BRANCHING: selezionare una variabile che ha valore frazionario nella soluzione ottimale del rilassamento  di P.L.  e suddividere la regione ammissibile in due sottoregioni imponendo i vincoli x≤µ;     x≥µ+1  , dove µ  è la parte intera della soluzione 

La decomposizione del  problema può essere rappresentata da una struttura gerarchica, detta albero di ricerca, in cui i discendenti di un nodo costituiscono i sottoproblemi; i nodi terminali (foglie) costituiscono la soluzione del problema iniziale.  

                              Caratteristiche principali del metodo BRANCH AND BOUND

• la ricerca della soluzione ottima avviene a passi successivi partendo da un nodo principale;

• in ciascun nodo viene considerata una soluzione parziale

• per ciascuna soluzione parziale viene calcolata una funzione di lower bound o di upper bound (minimizzazione o massimizzazione)

• le soluzioni parziali vengono costruite tramite un albero

• l'algoritmo termina quando viene trovata una soluzione che soddisfi i vincoli prefissati

Branch & Bound è un metodo di enumerazione implicita di tipo  esatto perchè evita di effettuare la partizione(branch) di quei nodi in cui il calcolo del bound assicura la determinazione di una soluzione peggiore di una soluzione ammissibile già nota.

Risoluzione di un problema di Programmazione lineare intera mediante il metodo Branch and bound utilizzando l'ambiente Derive

x , y interi

La soluzione ottima del problema è z=23 , in corrispondenza del vertice M(3,4).

Il grafico evidenzia le sottoregioni ammissibili, ottenute suddividendo la regione ammissibile OABC del problema rilassato di P.L. associato al problema di P.L.I.

  STRUTTURA AD ALBERO