Lagrange Relaxation
Limiti Inferiori (Lower Bounds)



Avere un Lower-Bound alla lunghezza del
cammino minimo da una garanzia della
qualità della soluzione trovata.
Tali limiti inferiori (Lower Bounds) in generale
vengono ottenuti risolvendo rilassamenti del
problema originale, nel senso che si ottimizza
su di un insieme contenente tutte le soluzioni
accettabili
Differenti tecniche di rilassamento producono
differenti soluzioni.
N.B. Se il limite inferiore che troviamo è anche un tour
valido, abbiamo trovato la soluzione ottima al
problema del TSP
Idea di Base

Selezioniamo un nodo a caso
dall’insieme delle città (ad es. il nodo
1), allora un tour consiste di uno
speciale spanning tree (albero di
copertura) sui rimanenti N-1 nodi più i
due archi che connettono il nodo 1 al
suo albero di copertura.
MST
Sui restanti
N-1 nodi
1
Connettiamo
Il nodo1 all’MST
MST
Rilassamento della Soluzione
Iniziale

A questo punto
otteniamo un
rilassamento del TSP se
prendiamo come
soluzioni accettabili
degli alberi di copertura
arbitrari sull’insieme di
nodi {2, …, N} più due
archi addizionali
incidenti il nodo 1.
Rilassamento della Soluzione
Iniziale
Tale grafo contiene precisamente un
circolo ed è chiamato 1-tree. Per
ottenere l’ 1-tree ottimo, calcoliamo
l’MST sull’insieme di nodi {2, …, N} che
può essere fatto in tempo polinomiale,
ad es. con l’algoritmo di Kruskal.
 Il limite inferiore ottenuto mediante
questo rilassamento (rilassamento 1tree) è abbastanza povero.
Vediamo come fare a migliorarlo…

Gestione dei Pesi

Per migliorare il bound bisogna
modificare i pesi in modo tale che i nodi
con grado
d_i = 2 siano piu’ attraenti degli altri.
Grado
troppo alto
Grado troppo basso
OK!
Gestione dei Pesi


Il nostro scopo dunque e’ trovare un
modo in cui modificare i pesi (i.e.: le
distanze), in modo tale che nell’MST
vengano preferiti i nodi di grado 2.
In seguito calcoleremo un nuovo albero
di copertura (MST) relativo alle
modifiche che abbiamo effettuato sui
pesi.
Gestione dei Pesi

Molto probabilmente
la sua lunghezza
sara’ maggiore,
dando in tal modo
un lower bound piu’
stretto (e quindi piu’
vicino) alla soluzione
del problema TSP.
Gestione dei Pesi


TEORICAMENTE: La procedura di aggiornamento
dei pesi, ricalcolo dell’algoritmo di kruskal viene
iterata fino a che la lunghezza dell’albero trovato
non cresce piu’ in maniera significativa, o fino a che
non troviamo un albero con tutti i nodi di grado 2
(i.e.: soluzione ottima).
OPERATIVAMENTE: reiteriamo la coppia di
operazioni


Calcolo del MST
Aggiornamento dei parametri
M volte , dove M è il numero di città
che fanno parte dell’istanza del TSP
L’Algoritmo fino a qui....
For i

1.
2.
3.

1: M
Calcola MST del grafo delle città (2 ... M ) –
ovvero su tutte tranne la prima.
Aggiungi la prima città collegandola all’MST
attreverso i due archi di peso minore.
Ricalcola i pesi relativi agli archi in modo da
favorire i nodi che nell’MST hanno solo due
collegamenti.(vedremo in seguito)
La lunghezza del MST finale è il lower
bound che cerchiamo.
Gestione Pesi

Oss.: in un tour esattamente 2 archi
sono incidenti ad un nodo, i.e: tutti i
nodi hanno un grado d_i = 2. Se
associamo ad ogni nodo i un peso p[i]
ed aggiorniamo i pesi degli archi, in
modo che
D[i][j] = D[i][j] + P[i] + P[j] , allora la
lunghezza di ogni cammino cresce di
2*somma di tutti i p_i.
Come scegliere i pesi




Oss.: I pesi vanno aggiunti ai nodi !
P[i] deve essere 0 quando il grado del
nodo è 2 , deve invece valere K != 0
quando il grado del nodo è diverso da
2.
Prima soluzione: P[i] = K *(deg[i] - 2 )
Vogliamo però tenere traccia del
passato.
Seconda soluzione:
P[i] = P[i] + K *(deg[i] - 2 )
Scelta della costante K



Ora il problema è scegliere K.
Vogliamo qualcosa di più
caratterizzante rispetto ad una
costante.
K deve tenere conto di:
1.
2.
3.
Iterazione corrente (1..M)
Relazione fra lunghezza del MST corrente e
lunghezza prevista del tour
Percentuale di nodi “buoni” (ovv. di grado 2)
nel MST corrente.
Iterazione corrente
Tener conto dell’iterazione corrente, vuol dire,
nello specifico, che vogliamo che K decresca
mano a mano che procediamo nell’iterazione
dell’algoritmo.
 Pertanto vi sarà nell’espressione di k un
lcalcolato
b 2
parametro decrescente 0 <
m
come segue:
lambda[m]
2*(M-m)/(M-1)

Numero delle città.
Iterazione corrente.
Relazione fra MST e Tour finale
previsto




Dobbiamo essere in grado di predire la
lunghezza finale del tour.
In che modo? Mediante una statistica.
Mandiamo in esecuzione sqrt(M) volte
2-opt, partendo ogni volta da una città
differente, e calcolandone la lunghezza.
La media di questi valori costituisce una
sovrastima della lunghezza finale del percorso
che indicheremo con U.
Nodi di grado 2 nel MST corrente

Vogliamo ovviamente tenere conto di
quale è il rapporto fra i nodi di grado 2
e gli altri, pertanto calcoliamo la
somma dei quadrati di (deg[i]-2) e
la poniamo come parametro di influenza
per lambda.
Criterio per l’aggiornamento dei
pesi
Incremento ad ogni passo.
Peso
all’iterazione
m+1
Aggiornamento pesi:
Calcolo dell’incremento ad ogni passo:
Stima della lunghezza
del cammino.
Grado del nodo nell’MST
Grado del nodo nell’MST
Parametro empirico
Peso complessivo del cammino
all’iterazione m
Riepilogo dei parametri

In particolare ad ogni passo di
aggiornamento dei parametri dovremo
calcolare due vettori e due valori:
1.
2.
3.
4.
Il vettore deg in cui calcoliamo il grado di
ogni nodo in relazione al MST corrente
Il parametro lambda relativo all’iterazione
corrente.
Il parametro t relativo all’iterazione corrente.
Il vettore P dei pesi dei nodi.
Soluzione Iniziale
Algoritmo in corso
Risultato Finale
Lagrange Relaxation:
Riduzione del numero di archi
Obbiettivo





Problema: calcolare un lower bound alla
lunghezza del tour ottimo.
Tecnica adottata: Lagrange relaxation.
Limiti della tecnica: computazionalmente
pesante su grafi dotati di un alto numero di
collegamenti.
Nuovo Obbiettivo: riduzione del numero
degli archi nel grafo di partenza.
Nuovo Problema: identificazione degli archi
da rimuovere.
Riduzione del numero di archi



Il punto cruciale dal punto di vista della
complessità computazionale riguarda il fatto
che l’elaborazione avviene su un grafo
completo, dotato quindi di nxn archi.
Intuitivamente gli archi che uniscono città
lontane fra loro non dovrebbero essere
candidate ad entrare a far parte del tour.
Vogliamo trovare un modo intelligente per
diminuire il numero degli archi da prendere in
considerazione.
Riduzione del numero di archi



Idea: fissiamo una soglia S << n che
limiti il numero di collegamenti per ogni
nodo.
Possiamo fissare ad esempio:
1/2
S = (n + log
n)/2
2
(un valore cioè fra la radice e il
logaritmo).
Chi sono i “vicini” di ogni nodo?
Riduzione del numero di archi




Per ogni nodo scegliamo di collegarlo agli S
nodi più vicini nel senso della distanza.
Per ogni nodo, cioè, scegliamo di preservare
gli S archi di peso (distanza) minore.
Operativamente ordiniamo ogni riga della
matrice delle distanze e scegliamo gli S di
peso minore.
Tale approccio può dare origine a due
problemi.
Riduzione del numero di archi


Problema 1: Alcuni degli archi che non
prendiamo in considerazione potrebbero
far parte effettivamente del tour.
Problema 2: Il grafo risultante dalla
sottrazione degli archi potrebbe non
essere connesso (e dunque non
sarebbe possibile calcolare MST).
Riduzione del numero di archi
In un grafo
completo di 10
nodi abbiamo
9 + 8 + ... +1
= 45 archi.
Molti archi non
saranno mai
candidati ad
entrare a far
parte del tour.
Riduzione del numero di archi
Riducendo il
numero di archi
in modo che ogni
nodo sia
collegato ai suoi
S = 2.73 ( i.e. 3)
vicini, abbiamo
solamente 18
collegamenti.
Riduzione del numero di archi
Se nel grafo
iniziale il nodo
centrale non
fosse stato
presente,
effettuando la
riduzione ci
saremmo trovati
con un grafo
formato da due
componenti.
Nearness


Vogliamo catturare il concetto di
vicinanza subordinata alla struttura del
grafo.
Vogliamo cioè introdurre una misura di
vicinanza (nearness) che rifletta la
probabilità di un dato arco di
appartenere al tour finale.
1-Tree



Ricorriamo nuovamente agli 1-tree.
Statisticamente si è osservato che un
tour ottimo contiene il 70%/80% di
archi di un 1-tree.
Dunque gli 1-tree sembrano prestarsi
bene come misura euristica della
“nearness”.
1-tree
Città
iniziale
Arco 2
Arco 1
La “vicinanza”
(nearness) nell’
entrare a far parte
del 1-tree è più
alta per l’arco 1,
che per l’arco 2.
Nearness



Gli archi cioè che appartengono (o sono
“vicini” all’appartenere) all’ 1-tree hanno una
buona probabilità di appartenere al tour
ottimo.
Al contrario, quegli archi che sono “lontani”
dall’appartenere all’ 1-tree hanno una
probabilità bassa di appartenere al tour
ottimo.
Identifichiamo la probabilità di un arco di
appartenere al tour finale con la sua
“vicinanza” ad essere scelto come arco per l’
1-tree.
Nearness

1.
2.
3.
4.
Formalmente:
Sia T un 1-tree di lunghezza L(T).
+
Denotiamo con T (i,j) l’ 1-tree a cui viene
richiesto di contenere l’arco (i,j).
Sia A un 1-tree, denotiamo con L(A) la
somma dei pesi (distanze) sugli archi di A.
Definiamo la nearness alpha di un arco
(i,j) come:
+
alpha[i][j] = L (T (i,j)) – L(T)
Nearness

Operativamente: data la lunghezza
dell’ 1-tree calcolato su tutto il grafo, la
nearness di un arco non è altro che
l’incremento in lunghezza richiesto per
contenere tale arco all’interno
dell’ 1-tree preservandone le proprietà.
Nearness


Oss1. In questo modo gli archi che
appartengono al MST hanno peso 0,
dunque apparterrano agli archi
selezionati per far parte del sottografo.
Oss2. Il sottografo risultante dalla
sottrazione degli archi è connesso.
Calcolo di alpha[i][j]


La nearness alpha[i][j] può essere
determinata per tutti gli archi (i,j).
Sia T un 1-tree minimo. Dalla
definizione di MST
è possibile ricavare
+
che un 1-tree T (i,j) contenente l’arco
(i,j) puo’ essere determinato usando
tre semplici regole.
+
Calcolo di T (i,j)
1.
2.
3.
+
Se (i,j) appartiene al MST, allora T (i,j) = T;
Se (i,j) ha 1 come nodo terminale allora
+
T (i,j) sarà ottenuto da T rimpiazzando il
piu’ lungo dei due archi di T incidenti con il
nodo 1 con (i,j).
Altrimenti si inserisce (i,j) in T . Questo crea
un ciclo contenente (i,j) nell’MST. In tal caso
+
otteniamo T (i,j) rimuovendo il più lungo
arco diverso da (i,j) nel ciclo.
Esempio


Calcolo 1-tree di un grafo G.
+
Calcolo di un T (i,j) per ognuno dei tre
casi del calcolo di alpha[i][j]
+
Calcolo di T (i,j)

1.
2.
Esempio:
Calcolo 1-tree di un grafo G.
+
Calcolo di un T (i,j) per ognuno dei tre
casi del calcolo di alpha[i][j]
Esempio: Calcolo dell’ 1-tree
1
2
3
2
3
4
4
5
Partenza: Grafo iniziale Completo
5
Passo1: Elimino la città 1
Esempio: Calcolo dell’ 1-tree
1
2
3
2
4
3
4
1-tree
5
Passo2: Calcolo MST
sui nodi restanti.
5
Passo3: Aggiungo la città 1,
collegandola ai due nodi più
vicini.
Esempio: classificazione archi

1.
2.
3.
4.
5.
Archi
appartenenti
all’ 1-tree:
(1,2)
(1,4)
(2,4)
(3,4)
(4,5)

1.
2.
3.
4.
5.
Archi non
appartenenti
all’ 1-tree:
(1,3)
(1,5)
(2,3)
(2,5)
(3,5)
+
Esempio: Calcolo di T (2,4)


L’arco (2,4) appartiene all’ 1-tree,
dunque si ricade nella regola 1.
In particolare: aggiungere (2,4) non
produce modifiche nell’MST, dunque
+
1
(2,4) = T.
2
T
3
4
+
T (2,4)
5
+
Esempio: Calcolo di T (1,3)



L’arco (1,3) non appartiene all’ 1-tree,
ma una delle sue estremità è il nodo 1,
dunque si ricade nella regola 2.
In particolare, dobbiamo aggiungere
l’arco (1,3) e togliere l’arco di peso
maggiore fra (1,2) e (1,4).
Eliminiamo (1,4) e inseriamo (1,3).
+
Esempio: Calcolo di T (1,3)
1
1
2
2
3
3
4
4
5
5
T
+
T (1,3)
+
Esempio: Calcolo di T (2,3)




L’arco (2,3) non appartiene all’ 1-tree,
nè una delle sue estremità è il nodo 1,
dunque si ricade nella regola 3.
In particolare, dobbiamo aggiungere
l’arco (1,3) al MST (non all’1-tree).
L’inserimento dell’arco (1,3) da origine
al ciclo (2,3,4) nel MST.
Eliminiamo (2,4) e inseriamo (2,3).
+
Esempio: Calcolo di T (1,3)
2
3
2
3
4
5
Partenza: MST
2
3
4
5
Passo 1: Inserimento
dell’arco (2,3)
4
5
Passo 2: eliminazione
dell’arco (2,4).
+
Esempio: Calcolo di T (2,3)
1
1
2
2
3
3
4
4
5
5
T
+
T (2,3)
Esempio: calcolo di alpha

In base a quanto visto fino ad adesso
possiamo calcolare tre valori per alpha:
1.
2.
3.
Alpha[2][4] = L(T (2,4)) – L(T) = 0, poichè
T = T (2,4) (r.1)
Alpha[1][3] = L(T(1,3)) – L(T) =
weight[1][3] – weight[1][4],
poichè T(1,3) = (T \ (1,4)) U (1,3) (r.2)
Alpha[2][3] = L(T(2,3)) – L(T) =
weight[2][3] – weight[2][4],
poichè T(1,3) = (T \ (2,4)) U (2,3) (r.3)
Alpha[i][j]: complessità


1.
2.
Problema: il caso 3 è pesante da
gestire in termini computazionali.
Oss.:
Sia beta[i][j] la lunghezza dell’arco da
rimuovere quando inseriamo l’arco
(i,j).
Allora:
alpha[i][j] = weight[i][j]-beta[i][j]
Calcolo di beta[i][j]

Se (j1,j2) è un arco
dell’MST, i è uno dei nodi
rimanenti e j1 è su quel
ciclo che si genera
aggiungendo l’arco (i,j2)
all’albero, allora
beta[i][j2] può essere
calcolato come il
massimo fra beta[i][j1] e
weight[j1][j2].
Calcolo di beta[i][j]



beta[i][j] indica il peso dell’arco da
rimuovere se forziamo il MST T a
contenere l’arco (i,j) rimanendo uno
spanning tree.
beta[i][j] viene calcolata sul MST (non
sull’ 1-tree). (i.e. i > 1, j >1)
Il calcolo di beta viene fatto in avanti
partendo cioè dal vertice 2 e crescendo.
Calcolo di beta[i][j]



Viene creato un vettore Dad[] in cui si salva il
valore del genitore del nodo relativamente al
MST.
Dad[j] = i se il nodo i è il padre di j nel MST.
Deve valere che Dad[j] = i  i<j,
altrimenti è necessario compiere una
permutazione degli indici (tale eventuale
riorganizzazione degli indici è lasciata agli implementatori).
Calcolo di beta[i][j]
1
2
3
2
3
4
5
Partenza: 1-tree
4
5
Passo 1: MST
Calcolo di beta[i][j]
Vettore Dad
2
3
4
5
2
nil
3
4
4
2
5
4
Riferimento al
genitore
Passo 2: Calcolo del vettore Dad
Attenzione !: Non e’ rispettato il vincolo
Dad[j] = i 
i<j
Calcolo di beta[i][j]
2
4
3
2
nil
3
2
4
3
5
3
5
Passo 3: Aggiusto gli indici
n.b. : In questo modo viene
Rispettato il vincolo
Dad[j] = i  i<j
Calcolo di beta[i][j]


Dunque per un dato nodo i tutti i valori
possono essere calcolati con una
complessità di O(n).
Algoritmo:
Calcolo di beta[i][j]
2
4
3
2
3
4
5
2
Not def.
Not def.
Not def.
Not def.
3
Not def.
Not def.
Not def.
Not def.
4
Not def.
Not def.
Not def.
Not def.
Not def.
Not def.
Not def.
Not def.
5
5
Passo 4: Inizializzazione della matrice b
Calcolo di beta[i][j]
2
2
4
3
3
4
5
2
-inf
Not def.
Not def.
Not def.
3
Not def.
Not def.
Not def.
Not def.
Not def.
Not def.
Not def.
Not def.
Not def.
Not def.
Not def.
Not def.
4
5
b
5
Passo 5: Calcolo di b[2][2]
Calcolo di beta[i][j]
n.b.: W[i][j] è il peso
dell’arco(i,j), i.e.:
quanto i è distante da j
2
4
3
2
3
2
-inf
3
4
5
4
5
(***)
Not def.
Not def.
Not def.
Not def.
Not def.
Not def.
Not def.
Not def.
Not def.
Not def.
Not def.
Not def.
Not def.
Not def.
Passo 6: i = 2, j = 3
5
(***): Max(b[2][dad[3]],W[3][dad[3]])
(***): Max(b[2][2],W[3][2]),(poiché dad[3] = 2)
(***): W[3][2], (poiché b[2][2] = - INF)
b
Calcolo di beta[i][j]
2
2
4
3
3
5
2
-inf
W[3][2]
(***)
Not def.
3
W[3][2]
Not def.
Not def.
Not def.
4
Not def.
Not def.
Not def.
Not def.
5
Not def.
Not def.
Not def.
Not def.
Passo 7: i = 2, j = 4
5
4
(***): Max(b[2][dad[4]],W[4][dad[4]])
(***): Max(b[2][3],W[4][3])
(***): Max(W[3][2],W[4][3])
b
Calcolo di beta[i][j]
2
2
4
3
4
5
2
-inf
W[3][2]
W[3][2]
Not def.
3
W[3][2]
Not def.
Not def.
Not def.
4
W[3][2]
Not def.
Not def.
Not def.
5
Not def.
Not def.
Not def.
Not def.
Passo 7: i = 2, j = 4
5
3
(***): Max(W[3][2],W[4][3])
(***): W[3][2]
b
Calcolo di beta[i][j]
2
2
4
3
3
5
2
-inf
W[3][2]
W[3][2]
(***)
3
W[3][2]
Not def.
Not def.
Not def.
4
W[3][2]
Not def.
Not def.
Not def.
5
Not def.
Not def.
Not def.
Not def.
Passo 8: i = 2, j = 5
5
4
(***): Max(b[2][dad[5]],W[5][dad[5]])
(***): Max(b[2][3],W[5][3])
(***): Max(W[3][2],W[5][3])
b
Calcolo di beta[i][j]
2
2
4
3
3
5
2
-inf
W[3][2]
W[3][2]
W[5][3]
3
W[3][2]
Not def.
Not def.
Not def.
4
W[3][2]
Not def.
Not def.
Not def.
5
W[5][3]
Not def.
Not def.
Not def.
b
Passo 8: i = 2, j = 5
5
4
(***): Max(W[3][2],W[5][3])
(***): W[3][2]
e così via per tutti gli altri archi…
Calcolo di beta[i][j]



Lo spazio in memoria impiegato per il calcolo
di beta[i][j] è O(N 2).
Vogliamo migliorare l’occupazione della
memoria, arrivando ad O(N).
Per fare questo utilizziamo un vettore b
(corrispondente alla vecchia matrice beta) ed
un vettore mark che indica il fatto che b[j] è
stato calcolato per il nodo i.
Calcolo di beta[i][j]

1.
2.
3.
La determinazione di b[j] può essere
fatta in due fasi.
b[j] viene calcolato per tutti i nodi j da
i fino alla radice (i.e. nodo 2).
Tali nodi vengono marcati con i.
Si utilizza un passo in avanti per
calcolare i valori di b rimanenti.
Calcolo di beta[i][j]
c(i,j) è la distanza fra i e j
Qui si esegue il calcolo di alpha[i][j]
(i.e.: alpha[i][j] = c(i,j) – b[j])
Conclusioni


I valori di alpha provvedono una buona
stima della probabilità che gli archi
vengano selezionati nel tour ottimo.
Più piccolo è il valore di alpha, più
grande è la probabilità che l’arco sia un
candidato per andare a comporre il tour.
Conclusioni

Usando tale definizione di nearness è
possibile limitare il numero degli archi
su cui mandare in esecuzione gli
algoritmi e ottenere lo stesso ottimi
risultati per il tour.