Branch-and-bound per T SP

(1)

Branch-and-bound per T SP

Anche qui, rispetto allo schema generale visto in precedenza dobbiamo specificare:

(2)

Branch-and-bound per T SP

come si calcola un lower bound su un sottinsieme;

(3)

Branch-and-bound per T SP

come si effettua il branching;

(4)

Branch-and-bound per T SP

come si effettua il branching;

come si individuano soluzioni ammissibili con cui,

eventualmente, aggiornare il valore dell’upper bound U B.

(5)

Richiamo: modello matematico TSP

min P

i∈V

P

j∈V : j6=i v_ijx_ij P

i∈V, i6=j x_ij = 1 ∀ j ∈ V P

j∈V, j6=i x_ij = 1 ∀ i ∈ V P

i∈U, j∈V \U x_ij ≥ 1 ∀ U ⊆ V : 2 ≤| U |≤| V | −2 x_ij ∈ {0, 1} ∀ i, j ∈ V, i 6= j

(6)

Lower bound L (S)

Supponiamo di voler ottenere un lower bound L(S) sull’intera regione ammissibile S del problema.

(7)

Lower bound L (S)

Per ottenere questo considereremo un rilassamento diverso da quello lineare. Il rilassamento che verrà preso in

considerazione è quello ottenuto omettendo i vincoli X

i∈U, j∈V \U

x_ij ≥ 1

(8)

Lower bound L (S)

Per ottenere questo considereremo un rilassamento diverso da quello lineare. Il rilassamento che verrà preso in

considerazione è quello ottenuto omettendo i vincoli X

i∈U, j∈V \U

x_ij ≥ 1

Si noti che l’omissione di alcuni vincoli è un caso

particolare di rilassamento lagrangiano in cui si pone λ = 0

(9)

Rilassamento

min P

i∈V

P

j∈V : j6=i v_ijx_ij P

i∈V, i6=j x_ij = 1 ∀ j ∈ V P

j∈V, j6=i x_ij = 1 ∀ i ∈ V

x_ij ∈ {0, 1} ∀ i, j ∈ V, i 6= j

(10)

Piccola modifica

In un circuito hamiltoniano non possiamo avere archi (i, i) (detti loop).

(11)

Piccola modifica

Possiamo comunque inserirli usando un opportuno

accorgimento consistente nell’attribuire a essi una distanza infinita, cioè v_ii = ∞.

(12)

Piccola modifica

Possiamo comunque inserirli usando un opportuno

accorgimento consistente nell’attribuire a essi una distanza infinita, cioè v_ii = ∞.

Con questa modifica avremo il seguente rilassamento:

min P

i∈V

P

j∈V v_ijx_ij P

i∈V x_ij = 1 ∀ j ∈ V P

j∈V x_ij = 1 ∀ i ∈ V

(13)

Come risolverlo?

Associamo al nostro grafo originario G = (V, A) un grafo bipartito G^′ = (V₁ ∪ V₂, A^′). I due insiemi V₁ e V₂ sono

ottenuti sdoppiando i nodi in V , cioè per ogni nodo i ∈ V se ne faranno due copie, il nodo a_i ∈ V₁ e il nodo b_i ∈ V₂

(14)

Come risolverlo?

Inoltre, ad ogni arco (i, j) ∈ A si associa l’arco (a_i, b_j) ∈ A^′, a cui si associa il valore v_ij.

(15)

Come risolverlo?

Inoltre, ad ogni arco (i, j) ∈ A si associa l’arco (a_i, b_j) ∈ A^′, a cui si associa il valore v_ij.

A questo punto il grafo G^′ è bipartito completo (includendo gli n archi (a_i, b_i), i ∈ V , corrispondenti ai loop con v_ii = ∞).

(16)

Sul grafo bipartito

x_ij ∈ {0, 1} ∀ (i, j) ∈ A ↔ x_ij ∈ {0, 1} ∀ (a_i, b_j) ∈ A^′

(17)

Sul grafo bipartito

x_ij ∈ {0, 1} ∀ (i, j) ∈ A ↔ x_ij ∈ {0, 1} ∀ (a_i, b_j) ∈ A^′ X

i∈V

X

j∈V

v_ijx_ij ↔ X

ai∈V¹

X

bj∈V²

v_ijx_ij

(18)

Sul grafo bipartito

i∈V

X

j∈V

v_ijx_ij ↔ X

ai∈V¹

X

bj∈V²

v_ijx_ij X

i∈V

x_ij = 1 ∀ j ∈ V ↔ X

ai∈V¹

x_ij = 1 ∀ b_j ∈ V₂

(19)

Sul grafo bipartito

i∈V

X

j∈V

v_ijx_ij ↔ X

ai∈V¹

X

bj∈V²

v_ijx_ij X

i∈V

x_ij = 1 ∀ j ∈ V ↔ X

ai∈V¹

x_ij = 1 ∀ b_j ∈ V₂ X

j∈V

x_ij = 1 ∀ i ∈ V ↔ X

bj∈V²

x_ij = 1 ∀ a_i ∈ V₁

(20)

Continua

Quindi, sul grafo G^′ possiamo riscrivere il nostro rilassamento in questo modo:

min P

ai∈V¹

P

bj∈V² v_ijx_ij P

ai∈V¹ x_ij = 1 ∀ b_j ∈ V₂ P

bj∈V² x_ij = 1 ∀ a_i ∈ V₁

x_ij ∈ {0, 1} ∀ a_i ∈ V₁, b_j ∈ V₂

(21)

Continua

Quindi, sul grafo G^′ possiamo riscrivere il nostro rilassamento in questo modo:

min P

ai∈V¹

P

bj∈V² v_ijx_ij P

ai∈V¹ x_ij = 1 ∀ b_j ∈ V₂ P

bj∈V² x_ij = 1 ∀ a_i ∈ V₁

x_ij ∈ {0, 1} ∀ a_i ∈ V₁, b_j ∈ V₂ Ribadiamo che nelle soluzioni ammissibili di questo

problema si consente anche la presenza di archi (a_i, b_i) che non corrispondono ad archi del problema T SP . Tuttavia, il fatto che a tali archi sia associato un valore +∞ ci

garantisce che nessuna soluzione ottima del problema conterrà tali archi.

(22)

Continua

Notiamo che il problema riformulato in questo modo è un problema di assegnamento dove i due insiemi da

accoppiare sono V₁ e V₂. Questo ci consente di utilizzare l’algoritmo ungherese per il calcolo del lower bound L(S).

(23)

Continua

Notiamo che il problema riformulato in questo modo è un problema di assegnamento dove i due insiemi da

accoppiare sono V₁ e V₂. Questo ci consente di utilizzare l’algoritmo ungherese per il calcolo del lower bound L(S). In particolare, notiamo che il calcolo del lower bound

richiede un tempo di calcolo polinomiale, come richiesto.

(24)

Continua

Una volta ottenuta una soluzione del problema di assegnamento con insieme di archi:

(a_i^k, b_j^k) k = 1, . . . , n

questa corrisponde alla seguente collezione di archi nel grafo originario:

(i^k, j^k) k = 1, . . . , n.

(25)

Continua

Sono possibili due casi:

la soluzione forma un circuito hamiltoniano, cioè

appartiene alla regione ammissibile S: in tal caso essa rappresenta anche la soluzione ottima del problema T SP ;

(26)

Continua

Sono possibili due casi:

la soluzione forma un circuito hamiltoniano, cioè

appartiene alla regione ammissibile S: in tal caso essa rappresenta anche la soluzione ottima del problema T SP ;

la soluzione ottenuta è una collezione di sottocircuiti.

(27)

Branching del nodo radice

Ci occuperemo ora di specificare come viene partizionata la regione ammissibile S in più sottinsiemi. Abbiamo visto che se non siamo nel caso fortunato in cui la soluzione del rilassamento è un circuito hamiltoniano, tale soluzione è una collezione di sottocircuiti.

(28)

Branching del nodo radice

Ci occuperemo ora di specificare come viene partizionata la regione ammissibile S in più sottinsiemi. Abbiamo visto che se non siamo nel caso fortunato in cui la soluzione del rilassamento è un circuito hamiltoniano, tale soluzione è una collezione di sottocircuiti.

Forniremo una semplice regola di suddivisione il cui scopo è quello di impedire il formarsi nei nodi figli di almeno uno dei sottocircuiti nella collezione.

(29)

Continua

Prendiamo il sottocircuito della collezione con meno archi (con scelta arbitraria se ve ne è più di uno). Indichiamo con {(i¹, j¹), (i², j²), . . . , (i^r, j^r)} gli archi di tale sottocircuito.

(30)

Continua

Il primo nodo figlio viene ottenuto imponendo che in esso non sia presente l’arco (i¹, j¹) (cioè si impone x_i¹_,j¹ = 0),

(31)

Continua

Il primo nodo figlio viene ottenuto imponendo che in esso non sia presente l’arco (i¹, j¹) (cioè si impone x_i¹_,j¹ = 0), il secondo nodo figlio viene ottenuto imponendo che sia

presente l’arco (i¹, j¹) ma non sia presente l’arco (i², j²) (cioè si impone x_i¹_,j¹ = 1, x_i²_,j² = 0),

(32)

Continua

Il primo nodo figlio viene ottenuto imponendo che in esso non sia presente l’arco (i¹, j¹) (cioè si impone x_i¹_,j¹ = 0), il secondo nodo figlio viene ottenuto imponendo che sia

presente l’arco (i¹, j¹) ma non sia presente l’arco (i², j²) (cioè si impone x_i¹_,j¹ = 1, x_i²_,j² = 0), e così via fino al

r-esimo figlio in cui si impone che siano presenti gli archi (i^k, j^k), k = 1, . . . , r − 1, ma non sia presente l’arco (i^r, j^r) (cioè si impone x_i^k_,j^k = 1, k = 1, . . . , r − 1, x_i^r_,j^r = 0).

(33)

Esempio

Sottocircuito 1 → 2 → 1.

(34)

Esempio

Sottocircuito 1 → 2 → 1. Tabella valori di x₁₂ e x₂₁

x12 x21

0 0

0 1

1 0

1 1

(35)

Esempio

x12 x21

0 0

0 1

1 0

1 1

Combinazione valori da escludere: x₁₂ = x₂₁ = 1 (corrisponde al sottocircuito).

(36)

Esempio

x12 x21

0 0

0 1

1 0

1 1

Primo nodo figlio → x₁₂ = 0.

(37)

Esempio

x12 x21

0 0

0 1

1 0

1 1

Primo nodo figlio → x₁₂ = 0.

Secondo nodo figlio → x₁₂ = 1 e x₂₁ = 0.

(38)

Sottinsiemi di S di forma particolare

Siano dati due sottinsiemi di archi A₀, A₁ ⊆ A con A₀ ∩ A₁ = ∅.

(39)

Sottinsiemi di S di forma particolare

Siano dati due sottinsiemi di archi A₀, A₁ ⊆ A con A₀ ∩ A₁ = ∅.

I sottinsiemi di S che ci interessano sono:

S(A⁰, A1) = {C = (V, A_C) ∈ S : ∀ (i, j) ∈ A¹ : (i, j) ∈ A_C, ∀ (i, j) ∈ A⁰ : (i, j) 6∈ A_C},

ovvero in S(A₀, A₁) abbiamo tutti i circuiti hamiltoniani che contengono sicuramente gli archi in A₁ e che sicuramente non contengono gli archi in A₀.

(40)

Nota bene

L’intera regione ammissibile S coincide con un particolare sottinisieme di forma S(A₀, A₁) con A₀ = A₁ = ∅, cioè:

S = S(∅, ∅)

(41)

Calcolo del lower bound per S (A

₀

, A

₁

)

Il calcolo si effettua come quello del lower bound per S e cioè risolvendo un problema di assegnamento. Rispetto al calcolo del lower bound per S vanno presi i seguenti due accorgimenti:

per ogni (i, j) ∈ A₀ si ponga v_ij = +∞: ciò impedisce la formazione della coppia (a_i, b_j) e quindi l’introduzione dell’arco (i, j);

(42)

Calcolo del lower bound per S (A

₀

, A

₁

)

Il calcolo si effettua come quello del lower bound per S e cioè risolvendo un problema di assegnamento. Rispetto al calcolo del lower bound per S vanno presi i seguenti due accorgimenti:

per ogni (i, j) ∈ A₀ si ponga v_ij = +∞: ciò impedisce la formazione della coppia (a_i, b_j) e quindi l’introduzione dell’arco (i, j);

per ogni (i, j) ∈ A₁ si escludano gli elementi a_i e b_j dal problema di assegnamento (essi sono già accoppiati tra loro). Si riduce di uno la dimensione del problema di

assegnamento.

(43)

Continua

Indichiamo con:

(a_i^k, b_j^k) k = 1, . . . , ℓ

la soluzione del problema di assegnamento. A questi

corrisponde il seguente insieme di archi nel grafo originario:

A_s = {(i^k, j^k), k = 1, . . . , ℓ}.

(44)

Continua

Indichiamo con:

(a_i^k, b_j^k) k = 1, . . . , ℓ

la soluzione del problema di assegnamento. A questi

corrisponde il seguente insieme di archi nel grafo originario:

A_s = {(i^k, j^k), k = 1, . . . , ℓ}.

Il lower bound per il sottinsieme S(A₀, A₁) è pari a L(S(A₀, A₁)) = X

(i,j)∈A¹∪As

v_ij.

(45)

Soluzione ammissibile?

Se l’insieme di archi A_s ∪ A₁ forma un circuito hamiltoniano, cioè appartiene alla regione ammissibile S, il suo valore

coincide con il valore del lower bound trovato e possiamo utilizzare tale valore per aggiornare, eventualmente, l’upper bound U B (NB: in tal caso il sottinsieme viene cancellato).

(46)

Soluzione ammissibile?

Se l’insieme di archi A_s ∪ A₁ forma un circuito hamiltoniano, cioè appartiene alla regione ammissibile S, il suo valore

coincide con il valore del lower bound trovato e possiamo utilizzare tale valore per aggiornare, eventualmente, l’upper bound U B (NB: in tal caso il sottinsieme viene cancellato).

Altrimenti l’insieme di archi A_s ∪ A₁ conterrà dei sottocircuiti.

(47)

Branching di S (A

₀

, A

₁

)

Si ripete quanto già visto per il nodo radice con una piccola differenza:

tra i sottocircuiti formati dagli archi A_s ∪ A₁ si prende quello che contiene meno archi in A_s (gli archi in A₁ sono già

fissati e non possono essere rimossi).

(48)

Esempio

Sia S(A₀, A₁) con:

A₀ = {(1, 7)} A₁ = {(1, 2); (2, 3)}, e sia

A_s ∪ A₁ = {(1, 2); (2, 3); (3, 4); (4, 1); (5, 6); (6, 7); (7, 5)}.

(49)

Esempio

A₀ = {(1, 7)} A₁ = {(1, 2); (2, 3)}, e sia

A_s ∪ A₁ = {(1, 2); (2, 3); (3, 4); (4, 1); (5, 6); (6, 7); (7, 5)}.

Dei due sottocircuiti in A₁ ∪ A_s, cioè:

1 → 2 → 3 → 4 → 1 5 → 6 → 7 → 5

(50)

Esempio

A₀ = {(1, 7)} A₁ = {(1, 2); (2, 3)}, e sia

A_s ∪ A₁ = {(1, 2); (2, 3); (3, 4); (4, 1); (5, 6); (6, 7); (7, 5)}.

Dei due sottocircuiti in A₁ ∪ A_s, cioè:

1 → 2 → 3 → 4 → 1 5 → 6 → 7 → 5 quello con meno archi in A_s è:

1 → 2 → 3 → 4 → 1

(51)

Continua

Indichiamo con {(i¹, j¹), (i², j²), . . . , (i^t, j^t)} gli archi del sottocircuito che appartengono ad A_s. Il primo nodo figlio viene ottenuto imponendo che in esso non sia presente l’arco (i¹, j¹) (cioè si impone x_i¹_,j¹ = 0),

(52)

Continua

Indichiamo con {(i¹, j¹), (i², j²), . . . , (i^t, j^t)} gli archi del sottocircuito che appartengono ad A_s. Il primo nodo figlio viene ottenuto imponendo che in esso non sia presente l’arco (i¹, j¹) (cioè si impone x_i¹_,j¹ = 0), il secondo nodo figlio viene ottenuto imponendo che sia presente l’arco (i¹, j¹) ma non sia presente l’arco (i², j²) (cioè si impone x_i¹_,j¹ = 1, x_i²_,j² = 0),

(53)

Continua

Indichiamo con {(i¹, j¹), (i², j²), . . . , (i^t, j^t)} gli archi del sottocircuito che appartengono ad A_s. Il primo nodo figlio viene ottenuto imponendo che in esso non sia presente l’arco (i¹, j¹) (cioè si impone x_i¹_,j¹ = 0), il secondo nodo figlio viene ottenuto imponendo che sia presente l’arco (i¹, j¹) ma non sia presente l’arco (i², j²) (cioè si impone

x_i¹_,j¹ = 1, x_i²_,j² = 0), e così via fino al t-esimo figlio in cui si impone che siano presenti gli archi (i^k, j^k), k = 1, . . . , t − 1, ma non sia presente l’arco (i^t, j^t) (cioè si impone

x_i^k_,j^k = 1, k = 1, . . . , t − 1, x_i^t_,j^t = 0).

(54)

Nell’esempio

Il primo nodo figlio viene ottenuto imponendo x₃₄ = 0.

(55)

Nell’esempio

Il primo nodo figlio viene ottenuto imponendo x₃₄ = 0.

Il secondo nodo figlio viene ottenuto imponendo x₃₄ = 1 e x₄₁ = 0.

(56)

Nota bene

Con questa regola di branching i nodi figli di un dato nodo continueranno ad essere sottinsiemi della regione

ammissibile di forma S(A₀, A₁).

(57)

Nota bene

Con questa regola di branching i nodi figli di un dato nodo continueranno ad essere sottinsiemi della regione

ammissibile di forma S(A₀, A₁).

Infatti, rispetto al nodo padre il primo nodo figlio aggiungerà l’arco (i¹, j¹) in A₀, il secondo nodo figlio aggiungerà l’arco (i¹, j¹) in A₁ e l’arco (i², j²) in A₀, il terzo nodo figlio

aggiungerà gli archi (i¹, j¹) e (i², j²) in A₁ e l’arco (i³, j³) in A₀, e così via.

(58)

Nell’esempio

Primo nodo figlio:

A₀ = {(1, 7); (3, 4)} A₁ = {(1, 2); (2, 3)}

(59)

Nell’esempio

Primo nodo figlio:

A₀ = {(1, 7); (3, 4)} A₁ = {(1, 2); (2, 3)}

Secondo nodo figlio:

A₀ = {(1, 7); (4, 1)} A₁ = {(1, 2); (2, 3); (3, 4)}

(60)

Osservazione

Nel calcolo del lower bound per un dato nodo dell’albero è possibile risparmiare computazioni sfruttando quelle già fatte per il nodo padre, in particolare, utilizzando la tabella finale individuata dall’algoritmo ungherese per il nodo padre e con le opportune modifiche per il nodo figlio. Questo

verrà illustrato tramite gli esempi.

(61)

Lower bound per TSP simmetrico

Vogliamo ora definire una nuova tecnica di calcolo di lower bound per il problema TSP nel caso simmetrico, ovvero il caso in cui:

v_ij = v_ji ∀ i, j ∈ V.

(62)

Definizione: 1-tree

Dato un grafo G = (V, A) non orientato e un suo nodo

a ∈ V , chiamiamo 1-tree un sottografo Q = (V, A_Q) di G con le seguenti proprietà:

(63)

Definizione: 1-tree

in A_Q ci sono esattamente due archi incidenti sul nodo a;

(64)

Definizione: 1-tree

se escludo da Q il nodo a e i due archi incidenti su di esso, mi rimane un albero sull’insieme di nodi V \ {a}.

(65)

Definizione: 1-tree

se escludo da Q il nodo a e i due archi incidenti su di esso, mi rimane un albero sull’insieme di nodi V \ {a}. In particolare, da questa definizione segue che | A_Q |=| V |.

(66)

Esempio

Dato il grafo con V = {a, b, c, d, e} e

A = {(a, b); (a, c); (b, c); (b, e); (c, d); (d, a); (d, e)}, il sottografo con

A_Q = {(a, b); (d, a); (b, c); (b, e); (d, e)}

è un 1-tree.

(67)

Osservazione

Si può notare che ogni circuito hamiltoniano è un 1-tree.

(68)

Osservazione

Infatti, in un circuito hamiltoniano su ogni nodo incidono esattamente due archi ed inoltre togliendo un nodo a qualsiasi e i due archi del circuito incidenti su di esso si ottiene un albero sull’insieme di nodi V \ {a}.

(69)

Osservazione

Infatti, in un circuito hamiltoniano su ogni nodo incidono esattamente due archi ed inoltre togliendo un nodo a qualsiasi e i due archi del circuito incidenti su di esso si ottiene un albero sull’insieme di nodi V \ {a}.

Il viceversa non è vero (lo 1-tree dell’esempio non è un circuito hamiltoniano).

(70)

Quindi ...

... se indichiamo con S^′ l’insieme degli 1-tree su un grafo G, tale insieme contiene la regione ammissibile S del

problema TSP.

(71)

Quindi ...

... se indichiamo con S^′ l’insieme degli 1-tree su un grafo G, tale insieme contiene la regione ammissibile S del

problema TSP.

In altre parole, il problema

Q=(V,AminQ)∈S^′

X

(i,j)∈AQ

v_ij

risulta essere un rilassamento per il problema TSP

simmetrico e la sua risoluzione restituisce un lower bound per il valore ottimo del problema TSP.

(72)

Calcolo del lower bound

Passo 1. Si risolva il problema MST sul grafo ottenuto scartando da G = (V, A) il nodo a prescelto e tutti gli

archi incidenti su di esso. Sia A_T l’insieme di archi della soluzione trovata;

(73)

Calcolo del lower bound

Passo 2. Si aggiungano ad A_T i due archi (a, k) e (a, h) a distanza minima tra tutti quelli incidenti sul nodo a

prescelto.

(74)

Calcolo del lower bound

Passo 2. Si aggiungano ad A_T i due archi (a, k) e (a, h) a distanza minima tra tutti quelli incidenti sul nodo a

prescelto.

Passo 3. Si restituisca Q = (V, A_Q) con A_Q = A_T ∪ {(a, k); (a, h)}.

(75)

Tempi di calcolo

Risoluzione del problema MST → in tempo polinomiale (ad esempio con l’algoritmo greedy).

(76)

Tempi di calcolo

Calcolo dei due valori minimi → in tempo polinomiale.

Quindi

(77)

Tempi di calcolo

Calcolo dei due valori minimi → in tempo polinomiale.

Quindi i tempi di calcolo complessivi sono polinomiali.

(78)

Nota bene

La scelta del nodo a è arbitraria.

(79)

Nota bene

Al costo di un maggiore sforzo computazionale, si possono anche calcolare | V | diversi lower bound scegliendo come nodo a tutti i nodi del grafo G e calcolando per ciascuno di essi il lower bound.

(80)

Nota bene

Al costo di un maggiore sforzo computazionale, si possono anche calcolare | V | diversi lower bound scegliendo come nodo a tutti i nodi del grafo G e calcolando per ciascuno di essi il lower bound.

Come lower bound complessivo del problema originario si utilizza il migliore (ovvero il più grande) tra tutti i | V | lower bound calcolati.

(81)

Lower bound per sottoproblemi

Per il calcolo del lower bound di un sottoproblema

S(A₀, A₁), si utilizza la stessa procedura imponendo però la presenza degli archi in A₁ ed escludendo quella degli archi in A₀ sia nella risoluzione del problema MST sia

nell’individuazione dei due archi incidenti sul nodo a.

(82)

Lower bound per sottoproblemi

In particolare, si può risolvere il problema MST sempre con l’algoritmo greedy ma:

(83)

Lower bound per sottoproblemi

inizializzando l’insieme di archi A_T non con l’insieme vuoto ma con tutti gli archi in A₁ non incidenti sul nodo a;

(84)

Lower bound per sottoproblemi

inizializzando l’insieme di archi A_T non con l’insieme vuoto ma con tutti gli archi in A₁ non incidenti sul nodo a;

non considerando gli archi in A₀ durante l’esecuzione

(85)

Inoltre ...

se in A₁ non sono presenti archi incidenti sul nodo a, metteremo in A_Q i due archi a distanza minima tra tutti quelli incidenti sul nodo a e al di fuori di A₀;

(86)

Inoltre ...

se in A₁ è già presente un arco incidente sul nodo a questo entrerà in A_Q insieme a quello a distanza

minima tra tutti quelli incidenti sul nodo a e al di fuori di A₀ e A₁;

(87)

Inoltre ...

se in A₁ è già presente un arco incidente sul nodo a questo entrerà in A_Q insieme a quello a distanza

minima tra tutti quelli incidenti sul nodo a e al di fuori di A₀ e A₁;

se in A₁ sono già presenti due archi incidenti sul nodo a, solo questi entreranno in A_Q.

(88)

Esempio

Supponiamo di avere il seguente problema del TSP simmetrico

1 2 3 4 5

1 − 5 8 3 5

2 5 − 4 6 2

3 8 4 − 10 3

4 3 6 10 − 1

5 5 2 3 1 −

(89)

Esempio

Supponiamo di avere il seguente problema del TSP simmetrico

1 2 3 4 5

1 − 5 8 3 5

2 5 − 4 6 2

3 8 4 − 10 3

4 3 6 10 − 1

5 5 2 3 1 −

Proviamo a calcolare il lower bound per il sottoproblema S(A₀, A₁) con A₀ = {(1, 3); (4, 5)} e A₁ = {(1, 5); (2, 4)}.

Utilizziamo come nodo a il nodo 1.

(90)

Continua

Per prima cosa dobbiamo risolvere il problema MST

sull’insieme di nodi V \ {1} imponendo la presenza dell’arco (2, 4) che è in A₁ ed escludendo quella degli archi in A₀.

(91)

Continua

Per prima cosa dobbiamo risolvere il problema MST

sull’insieme di nodi V \ {1} imponendo la presenza dell’arco (2, 4) che è in A₁ ed escludendo quella degli archi in A₀.

Utilizzando l’algoritmo greedy con A_T inizializzato con gli archi in A₁ non incidenti sul nodo 1 (in questo caso il solo arco (2, 4)) ed escludendo la possibilità di inserire gli archi in A₀, arriviamo al seguente albero su V \ {1}

A_T = {(2, 4); (2, 5); (3, 5)}.

(92)

Continua

Notiamo che in A₁ è presente l’arco (1, 5) incidente sul nodo 1.

(93)

Continua

Notiamo che in A₁ è presente l’arco (1, 5) incidente sul nodo 1.

Ad A_T dobbiamo quindi aggiungere, oltre a questo arco (1, 5), l’arco a distanza minima tra tutti quelli incidenti sul nodo 1 e al di fuori di A₀ e A₁, ovvero (1, 4).