Algoritmo di Riduzione del Gap Branch and Bound

uni
Questo è un algoritmo di Complessità esponenziale usato per i Problema di Programmazione Lineare Intera (PLI) booleani (anche se si può usare per quelli interi).
Si fonda sul concetto di Albero di Enumerazione Totale.
È possibile applicarlo a qualsiasi Problema di Programmazione Lineare Intera (PLI), basta che abbia una $V_I$ ed una $V_S$ facilmente calcolabili.

Algoritmo

Parto con $V_i$ come valore corrente.
Tramite le regole di taglio:
Taglio un ramo e scopro se tra le soluzioni sotto quel ramo ce ne è una migliore del valore corrente, in caso contrario taglio via quel ramo e quindi nego la variabile di quel ramo.
Se invece trovo un valore migliore, lo tengo come valore corrente, taglio il ramo e fisso la variabile di quel ramo.
Tagliare: visita implicita del sottoalbero, ovvero ho tutte le informazioni che mi servono su tutte le foglie del sottoalbero.
Questo algoritmo finisce quando ho fatto una visita implicita per ogni ramo.

Regole di Taglio (Branch)

minimo (TSP)

con $P_{ij}$ stadio $i$, ramo $j$.

1. $P_{ij}=\varnothing ?taglio$
   devo controllare poiché più scendo e più restringo la Regione Ammissibile (aggiungo vincoli).
2. $V_I(P_{ij})\ge V_S(P)?taglio$
   Calcolo $V_I(P_{ij})$, ovvero l’ottimo del Rilassato continuo di $P_{ij}$, se è maggiore del valore corrente posso tagliare.
3. se $V_I(P_{ij})<V_S(P)$ e $V_I(P_{ij})ammissibile$ allora aggiorno $V_S$ con $V_I(P_{ij})$

massimo (TSP)

Tenendo come riferimento il Problema dello Zaino (quindi di $max$)
con $P_{ij}$ stadio $i$, ramo $j$.

1. $P_{ij}=\varnothing ?taglio$
2. $V_S(P_{ij})\le V_I(P)?taglio$
   Calcolo $V_S(P_{ij})$, ovvero l’ottimo del Rilassato continuo di $P_{ij}$, se è minore o uguale del valore corrente posso tagliare.
3. se $V_S(P_{ij})>V_I(P)$ e $V_S(P_{ij})ammissibile$($\in Z^n$ ovvero componenti intere) allora aggiorno $V_I$ con $V_S(P_{ij})$ allora scatta la regola 2 e taglio.