ALCUNI ESERCIZI SUL PROBLEMA DEL COMMESSO VIAGGIATORE SIMMETRICO.

(1)

ALCUNI ESERCIZI SUL PROBLEMA DEL COMMESSO VIAGGIATORE SIMMETRICO.

CORSO DI RICERCA OPERATIVA II

ESERCIZIO 1. Le seguenti matrici triangolari alte rappresentano altrettante istanze del problema del commesso viaggiatore simmetrico (S-TSP). Risolverle applicando l’algoritmo di branch and bound con rilassamento basato sul 1-tree di costo minimo.







1 2 3 4 5 6

1 4 3 7 5 9

2 6 9 1 2

3 8 4 3

4 2 4

5 7













1 2 3 4 5 6

1 6 2 5 7 1

2 3 1 7 8

3 4 9 2

4 5 5

5 4







(a) (b)







1 2 3 4 5 6

1 3 8 2 9 9

2 5 6 7 8

3 8 7 2

4 2 3

5 8













1 2 3 4 5 6

1 5 9 5 2 7

2 5 5 7 4

3 8 1 7

4 8 7

5 9







(c) (d)

ESERCIZIO 2. Per le matrici dell’esercizio 1, calcolare l’1-tree di costo minimo con a = 1 e, partendo dal vettore λ 1 = · · · = λ 6 = 0, calcolare l’aggiornamento dei moltiplicatori λ i ed il nuovo valore del lower bound.

1

(2)

2 CORSO DI RICERCA OPERATIVA II

Soluzioni

1. (a) Come primo passo si calcola il rilassamento al nodo radice (nodo 1). Utilizzando, arbitrariamente, a = 1, si determina l’1-tree di costo minimo formato dagli archi A Q = {(1, 2), (1, 3), (2, 5), (2, 6), (3, 6), (4, 5)}, dove A T = {(2, 5), (2, 6), (3, 6), (4, 5)}

`e l’albero di supporto a costo minimo determinato per il sottografo indotto dai nodi V \ {1}, e (1, 2), (1, 3) sono i due archi di costo minimo incidenti sul nodo a = 1.

Risulta LB 1 = P

(i,j)∈A

Q

v _ij = 15. Si osserva che questo 1-tree non corrisponde ad un tour ammissibile, in quanto esso contiene il ciclo (1, 2, 6, 3, 1) — archi (1, 2), (2, 6), (3, 6), (1, 3). Si pone quindi l’upper bound iniziale UB = −∞ e si procede al branch.

Il branch del nodo 1 produce i seguenti nodi figli.

2 : A 0 = {(1, 2)}, A 1 = ∅;

3 : A 0 = {(2, 6)}, A 1 = {(1, 2)};

4 : A ₀ = {(3, 6)}, A 1 = {(1, 2), (2, 6)};

5 : A 0 = {(1, 3)}, A 1 = {(1, 2), (2, 6), (3, 6)}.

Ai nodi 2, tenuto conto dei vincoli imposti da A 0 , A 1 , si generano gli 1-tree di costo minimo

2 : A Q = {(1, 3), (1, 5), (1, 2), (2, 6), (3, 6), (4, 5)}, LB 2 = v(A Q ) = 16;

3 : A Q = {(1, 2), (1, 3), (2, 5), (3, 6), (4, 5), (4, 6)}, LB 3 = v(A Q ) = 17;

4 : A _Q = {(1, 2), (1, 3), (2, 5), (2, 6), (3, 5), (4, 5)}, LB 3 = v(A Q ) = 16;

5 : A _Q = {(1, 2), (1, 5), (2, 5), (2, 6), (3, 6), (4, 5)}, LB 4 = v(A Q ) = 17.

Valutando in sequenza i nodi cos`ı ottenuti, si nota che al nodo 3 l’insieme di archi A Q individuato corrisponde al ciclo hamiltoniano (1, 2, 5, 4, 6, 3, 1), di costo z = 17 > UB. Quindi si pone UB = 17 e si salva quest’ultima come migliore soluzione ammissibile nota. Il nodo 3 viene chiuso per ottimalit` a.

Successivamente, valutando il nodo 5, risulta LB 5 = 17 ≥ UB, quindi il nodo 5 viene chiuso.

Rimangono aperti i nodi 2 e 4. Si pu` o scegliere il nodo 4 per continuare l’esplorazione. La soluzione del rilassamento del nodo 4 presenta il ciclo (1, 3, 5, 2, 1) creato dagli archi (2, 5), (3, 5), (1, 3), (1, 2). L’arco (1, 2) `e gi` a fissato; per quanto riguarda i rimanenti archi, si ottengono i seguenti nodi.

6 : A 0 = {(3, 6), (2, 5)}, A 1 = {(1, 2), (2, 6)};

7 : A 0 = {(3, 6), (3, 5)}, A 1 = {(1, 2), (2, 6), (2, 5)};

8 : A ₀ = {(3, 6), (1, 3)}, A 1 = {(1, 2), (2, 6), (2, 5), (3, 5)}.

Il nodo 6 viene chiuso in quanto

A _Q = {(1, 2), (1, 3), (2, 6), (3, 5), (3, 5), (4, 6)}, LB 6 = v(A Q ) = 19 ≥ UB (si noti che rappresenta anche una soluzione ammissibile, ma di valore peggiore di UB) mentre i nodi 7 e 8, senza necessit` a di risolvere il rilassamento, vengono chiusi per non-ammissibilit` a in quanto il nodo 2 del grafo presenta grado 3 causato dagli archi in A 1 .

Rimane aperto il nodo 2, con LB 2 = 16 < UB; la soluzione del rilassamento del

nodo 2 presenta il ciclo (2, 6, 3, 1, 5, 2), formato dagli archi (2, 6), (3, 6), (1, 3), (1, 5),

(3)

ALCUNI ESERCIZI SUL PROBLEMA DEL COMMESSO VIAGGIATORE SIMMETRICO. 3

1 2 3 4 5

6 7 8

9 . . . 13

Figure 1. Albero di branch per l’esercizio 1(a).

(2, 5). Effettuando il branch si ottengono i seguenti nodi.

9 : A 0 = {(1, 2), (2, 6)}, A 1 = ∅;

10 : A 0 = {(1, 2), (3, 6)}, A 1 = {(2, 6)};

11 : A 0 = {(1, 2), (1, 3)}, A 1 = {(2, 6), (3, 6)};

12 : A 0 = {(1, 2), (1, 5)}, A 1 = {(2, 6), (3, 6), (1, 3)};

13 : A 0 = {(1, 2), (2, 5)}, A 1 = {(2, 6), (3, 6), (1, 3), (1, 5)}.

Valutandoli in sequenza, risulta:

9 : A Q = {(1, 3), (1, 5), (2, 5), (3, 6), (4, 5), (4, 6)}, LB 9 = 18 > UB;

10 : A Q = {(1, 3), (1, 5), (2, 5), (2, 6), (3, 4), (4, 5)}, LB 10 = 17 ≥ UB;

11 : A Q = {(1, 4), (1, 5), (2, 5), (2, 6), (3, 6)}, LB 11 = 20 > UB;

12 : A Q = {(1, 3), (1, 4), (2, 5), (2, 6), (3, 6), (4, 5)}, LB 12 = 18 > UB;

13 : A Q = {(1, 3), (1, 5), (2, 6), (3, 5), (3, 6), (4, 6)}, LB 13 = 21 > UB . Tutti questi nodi vengono chiusi. Non essendoci pi` u nodi aperti, la soluzione cor- rispondente all’upper bound risulta ottima, con ottimo z ^∗ = 17.

(b) z ^∗ = 16.

(c) z ^∗ = 22.

(d) z = ^∗ = 24.

2. (a) Si pu` o applicare il seguente schema iterativo di aggiornamento, dove LB(λ) = X

i=1

λ i + X

(i,j)∈A

Q

(v ij − λ i − λ j ),

con Q(V, A Q ) = 1-tree di costo minimo calcolato sui costi ¯ v ij − λ i − λ j .

1: Fissa il valore iniziale di λ 1 , . . . , λ _n ;

2: Poni LB := LB(λ), δ = 0;

3: repeat

4: λ := λ + δ;

5: Calcola la variazione δ = (δ 1 , . . . , δ n ) come δ _i = 2 − deg _Q (i)

6: Calcola LB(λ + δ);

7: LB := max{LB, LB(λ + δ)};

8: until LB(λ + δ) ≤ LB(λ);

9: return LB;

Partendo con λ 1 , . . . , λ ₆ = 0, si ottiene inizialmente l’1-tree con

A _Q = {(1, 2), (1, 3), (2, 5), (2, 6), (3, 6), (4, 5)}, LB(λ) = 15.

(4)

4 CORSO DI RICERCA OPERATIVA II

Applicando lo schema di aggiornamento, si modificano i moltiplicatori λ 2 , λ 4 . λ 2 := λ 2 + (2 − deg _Q (2)) = 0 + (2 − 3) = −1,

λ 4 := λ 4 + (2 − deg _Q (4)) = 0 + (2 − 1) = 1;

gli altri moltiplicatori rimangono invariati, quindi λ = (0, −1, 0, −1, 0, 0). Rical- colando l’1-tree di costo minimo sui costi ¯ v _ij − λ _i − λ _j si ottiene

¯ v ij =







1 2 3 4 5 6

1 5 3 6 5 9

2 7 9 2 3

3 7 4 3

4 1 3

5 7







=⇒ A Q = {(1, 2), (1, 3), (2, 5), (2, 6), (3, 6), (4, 5)}, LB(λ) = 17.

Ripetendo l’aggiornamento, si aggiornano ancora i moltiplicatori λ 2 , λ 4 , quindi λ = (0, −2, 0, 2, 0, 0), da cui

¯ v ij =







1 2 3 4 5 6

1 6 3 5 5 9

2 8 9 3 4

3 6 4 3

4 0 2

5 7







=⇒ A Q = {(1, 3), (1, 4), (2, 5), (3, 6), (4, 5), (4, 6)}, LB(λ) = 16.

Lo schema termina quindi con LB = 17.

(b) Si ottiene, successivamente:

λ = (0, 0, 0, 0, 0, 0) =⇒ LB(λ) = 13 λ = (0, 0, −1, 1, 1, −1) =⇒ LB(λ) = 16

λ = (0, 0, −2, 1, 2, −1) =⇒ LB(λ) = 16 =⇒ STOP, LB = 16.

(c) Si ottiene, successivamente:

λ = (0, 0, 0, 0, 0, 0) =⇒ LB(λ) = 17 λ = (0, 0, 0, −1, 1, 0) =⇒ LB(λ) = 19 λ = (0, 0, 0, −2, 2, 0) =⇒ LB(λ) = 21

λ = (0, 0, 0, −3, 3, 0) =⇒ LB(λ) = 20 =⇒ STOP, LB = 21.

(d) Si ottiene, successivamente:

λ = (0, 0, 0, 0, 0, 0) =⇒ LB(λ) = 22 λ = (0, −2, 0, 1, 0, 1) =⇒ LB(λ) = 23

λ = (0, −1, 0, 1, 0, 0) =⇒ LB(λ) = 23 =⇒ STOP, LB = 23.