📈 Ottimizzazione

Search

SearchSearch

Metodo del Branch and Bound

Mar 06, 2024, 4 min read

Metodo Branch and Bound

È un metodo molto utilizzato per risolvere problemi PLI.

Si basa sul partizionamento del poliedro del (RL). Si risolvono quindi i sottoproblemi (lineari) sugli insiemi della partizione.

Dato un problema PLI:

Problema PLI

Osservazione

Osservazione

La regione ammissibile di un problema intero non è convessa. In generale possono esservi alcune variabili continue e alcune intere. Si parla in tal caso di PLI mista (che non trattiamo)

Esempio

Se risolviamo il problema senza vincolo di interezza, l’ottimo sarebbe .

Altrimenti:

  • Soluzione ottima intera:
  • Soluzione arrotondata:

Come è ovvio vedere, non è possibile risolvere il problema intero eliminando il vincolo di interezza e risolvendo il problema continuo approssimando la soluzione.

Bisogna necessariamente risolvere il problema intero.

Relazioni problemi lineari < - > interi

Rilassamento Lineare

Dato un problema PLI (definito sopra), è possibile ottenere un Rilassamento Lineare (RL), o continuo:

  • Risulta che , cioè la regione ammissibile del problema di PLI è data dalla soluzione intera del poliedro P.

  • Inoltre , cioè la reigone ammissibile del problema PLI è sempre contenuta nel poliedro P.

Si ha che il valore ottimo di (RL) è sempre del valore ottimo di (PLI):

Infine:

Se la soluzione ottima di (RL) è intera è soluzione del problema (PLI).

Link to original

e il suo rilassamento lineare:

Rilassamento Lineare

Dato un problema PLI (definito sopra), è possibile ottenere un Rilassamento Lineare (RL), o continuo:

  • Risulta che , cioè la regione ammissibile del problema di PLI è data dalla soluzione intera del poliedro P.

  • Inoltre , cioè la reigone ammissibile del problema PLI è sempre contenuta nel poliedro P.

Si ha che il valore ottimo di (RL) è sempre del valore ottimo di (PLI):

Infine:

Se la soluzione ottima di (RL) è intera è soluzione del problema (PLI).

Link to original

Partizioniamo nei sottoinsiemi e risolviamo:

Il valore ottimo del problema (PLI) indicato con

Procedimento

Il metodo prevede di partizionare in maniera ricorsiva e risolvere i vari sottoproblemi e i rispettivi (RL).

Si partiziona ogni partizione fino a quando si trova una sol intera o un sottoproblema risulta inammissibile.

Il metodo individua anche le partizioni sulle quali non occorre risolvere il sottoproblema.

Non è un metodo di enumerazione totale.

Descrizione del Metodo

Si basa su due operazioni:

  • Bounding: Si risolve un (RL) del problema di (PLI) e si ottiene un lower bound per il valore ottimo intero;
  • Branching: La soluzione fornita dal (RL) indica come effettuare il partizionamento

Sia la soluzione di non intera. avrà qualche componente frazionaria, che chiamiamo

Questa è detta variabile di branch, e genera due sottoproblemi:

Se ci sono più componenti frazionarie si può:

  1. Scegliere quella con parte frazionaria più vicina a
  2. Scegliere quella con coefficiente della più elevato.
    • Questo rende più probabile trovare la soluzione intera nel ramo e chiudere invece il ramo

Criteri di Potatura

Cioè criteri per chiudere nodi. Ne esistono 3:

  1. Il vincolo di branch è incompatibile con i vincoli del problema, che risulta inammissibile;
  2. Si trova una soluzione intera;
  3. Chiusura per bounding: si risolve un sottoproblema lineare continuo che dà una soluzione non intera e il suo valore ottimo è peggiore del valore ottimo corrente del problema intero

Osservazione

Il branching può essere binario, ma anche di dimensioni maggiori, dipende dal problema.

Strategie di visita

Visita in Profondità (DFS)

Si risolve il primo figlio di ogni nodo, fino a quando non si deve risalire.

Minimizza il numero di nodi aperti da esplorare, e ha bassi requisiti di memoria. Inoltre, si ottiene rapidamente una soluzione intera.

Lo svantaggio è dovuto al fatto che si possono dover risolvere molti problemi (e quindi nodi da esplorare)

Visita per bound migliore

Si risolve prima il problema con valore ottimo migliore. Se minimizziamo, scegliamo il problema con lower bound inferiore.

In tal caso, si esplorano meno nodi, ma ne restano molti aperti. C’è maggiore richiesta di memoria, ed è possibile che se si arresta l’algoritmo prima non si trovi una soluzione intera.

Difatti, risulta più efficiente unire le due strategie:

  • Si fissa il numero max di nodi aperti consentiti;
  • Si applica il best bound;
  • Raggiunto il limite di nodi aperti, si procede con l’esplorazione DFS.

Upper Bound

Un upper bound per il valore ottimo del problema intero si ottiene calcolando la nella prima soluzione intera disponibile.

Dato

Lower BoundUpper Bound
Risolvendo i (RL)Valore della f.o. calcolato in una sol. intera

Problema di Massimizzazione

I (RL) forniscono degli upper bound per il valore ottimo intero.

La f.o. dà invece un lower bound

Cioè il contrario di quanto detto prima.

Chiusura per Bounding

Come prima, se il valore ottimo ottenuto risolvendo un sottoproblema con soluzione non intera è minore del valore ottimo corrente si chiude il nodo.

Esplorazione per Best Bound

Si seglie il sottoproblema con ottimo maggiore.

Graph View

Backlinks