TSP con eliminazione di sottocicli
Un commesso viaggiatore deve visitare 7 clienti in modo da minimizzare la distanza per- corsa. Le distanze (in Km) tra ognuno dei clienti sono come segue:
1 2 3 4 5 6 7
1 - 86 49 57 31 69 50
2 - 68 79 93 24 5
3 - 16 7 72 67
4 - 90 69 1
5 - 86 59
6 - 81
(la matrice delle distanze `e simmetrica).
Formulare un modello di PLI e proporre un programma in AMPL che risolva il prob- lema.
Approfondimento (opzionale) Si parli di un possibile approccio euristico per la
soluzione del TSP, considerando che sulla matrice delle distanze vale la disuguaglianza
triangolare.
Soluzione
Formalizziamo il problema come un grafo diretto completo G(V, A) dove V sono i clienti e A sono tutti gli archi possibili tra i nodi in V . I pesi sugli archi sono le distanze tra i clienti. Si deve cercare un cammino di peso minimo che tocchi tutti i nodi una e una sola volta.
Formulazione
• Parametri:
1. sia V l’insieme dei clienti da visitare;
2. per ogni i, j ∈ V sia d
ijla distanza tra il cliente i e il cliente j.
• Variabili: per ogni i 6= j ∈ V , sia x
ij= 1 se il commesso viaggia direttamente tra i e j, e 0 altrimenti (x
ij∈ {0, 1}).
• Funzione obiettivo:
min X
i6=j∈V
d
ijx
ij.
• Vincoli:
X
j∈V,j6=i
x
ij= 1 ∀i ∈ V (solo un successore) X
i∈V,i6=j
x
ij= 1 ∀j ∈ V (solo un predecessore) X
i∈S,j∈V \S
x
ij≥ 1 ∀S ( V (nessun sottociclo)
x
ij∈ {0, 1} ∀i 6= j ∈ V.
L’ultimo vincolo dice che per ogni partizione dei vertici, ci dev’essere almeno un arco nel taglio corrispondente. Questo impedisce la formazione di sottocicli non triviali (che ovviamente definirebbero una partizione dei vertici con un taglio associato vuoto). Dato che il numero dei sottoinsiemi propri S di un insieme V `e un numero esponenziale nella cardinalit`a di V , la dimensione di un’istanza del problema esposto sopra `e esponenziale (e dunque non accettabile). Bisogna dunque adottare un’opportuna strategia di soluzione.
Inizialmente, il problema viene rilassato cancellando completamente il vincolo “nessun
sottociclo” (in tal modo la dimensione dell’istanza `e polinomiale). Il rilassamento ottenuto
viene risolto tramite le comuni tecniche di PLI. La soluzione trovata pu`o non essere
ammissibile per il vincolo “nessun sottociclo”: ovvero, potrebbero esserci dei sottocicli
non banali. Cerchiamo quindi il sottociclo pi` u piccolo, inseriamo nel problema rilassato
un solo vincolo della classe di vincoli “nessun sottociclo” in modo che il sottociclo trovato
venga “rotto”, e ri-ottimizziamo il problema. Si continua iterativamente finch´e la soluzione
non presenta pi` u alcun sottociclo. A quel punto la soluzione trovata `e quella ottima.
Tentiamo prima un approccio “manuale” alla generazione dei cicli da rompere. Ri- solviamo prima il modello seguente.
Modello AMPL
# modello per tsp
param n > 0, integer;
set V := 1..n;
param d{V,V} >= 0;
param numerocicli >= 0, integer, default 0;
set ciclo{1..numerocicli};
var x{V,V} binary;
minimize costociclo : sum{i in V, j in V : i != j} d[i,j]*x[i,j];
subject to successore {i in V} : sum{j in V : i != j} x[i,j] = 1;
subject to predecessore {j in V} : sum{i in V : i != j} x[i,j] = 1;
subject to nocicli {k in 1..numerocicli} :
sum{i in ciclo[k], j in V diff ciclo[k]} x[i,j] >= 1;
Dati AMPL
# tsp.dat param n := 7;
param d : 1 2 3 4 5 6 7 :=
1 0 86 49 57 31 69 50 2 0 0 68 79 93 24 5
3 0 0 0 16 7 72 67
4 0 0 0 0 90 69 1
5 0 0 0 0 0 86 59
6 0 0 0 0 0 0 81
7 0 0 0 0 0 0 0 ;
Per risolverlo, usiamo il seguente file .run, in cui si inizializza la matrice delle distanze in modo che sia simmetrica.
Algoritmo AMPL: file tsp-simple.run
# leggi modello e dati model tsp.mod;
data tsp.dat;
# rendi simmetrica la matrice delle distanze for {i in V, j in V : i > j} {
let d[i,j] := d[j,i];
}
# risolvi
option solver cplex;
solve;
# stampa
display costociclo;
display x;
Si noti che siccome ciclo e‘ inizializzato a una lista di insiemi vuoti, i vincoli di rottura dei sottocicli di fatto non sono stati inseriti. Otteniamo la soluzione seguente, che corrisponde infatti a tre cicli distinti: (1, 3, 5, 1), (2, 6, 2) e (4, 7, 4).
Soluzione CPLEX (non ottima)
costociclo = 137
x [*,*]
: 1 2 3 4 5 6 7 :=
1 0 0 1 0 0 0 0
2 0 0 0 0 0 1 0
3 0 0 0 0 1 0 0
4 0 0 0 0 0 0 1
5 1 0 0 0 0 0 0
6 0 1 0 0 0 0 0
7 0 0 0 1 0 0 0 ;
In pratica, abbiamo la situazione come nella figura qui sotto.
1
3 5
2
6
4
7
Aggiungiamo perci`o un vincolo di rottura del sottociclo (1, 3, 5, 1) al modello: per S = {1, 3, 5} si impone P
i∈S,j∈V \S
x
ij≥ 1. In AMPL, `e sufficiente aggiungere le istruzioni seguenti nel file tsp-simple.run, prima dell’istruzione “solve;”, e risolvere nuovamente il modello lanciando ampl < tsp-simple.run.
let numerocicli := 1;
let ciclo[1] := { 1, 3, 5 };
Si ottiene la soluzione seguente, che essendo un ciclo Hamiltoniano, `e ottima.
Soluzione CPLEX (ottima)
costociclo = 153
x [*,*]
: 1 2 3 4 5 6 7 :=
1 0 0 0 0 0 1 0
2 0 0 0 0 0 0 1
3 0 0 0 0 1 0 0
4 0 0 1 0 0 0 0
5 1 0 0 0 0 0 0
6 0 1 0 0 0 0 0
7 0 0 0 1 0 0 0 ;
La ciclo Hamiltoniano ottimo `e (1, 6, 2, 7, 4, 3, 5, 1), raffigurato sotto. In generale, la soluzione non `e unica (possono esistere pi` u cicli Hamiltoniani con lo stesso costo), quindi si potrebbe trovare una soluzione diversa da questa.
1
3 5
2
6
4
7
Descriviamo ora un algoritmo in AMPL per la generazione automatica dei sottocicli da rompere (per eseguirlo, usare il comando ampl < tsp.run).
Algoritmo AMPL: file tsp.run
# tsp.run - algoritmo per la rottura dei sottocicli
# usa cplex e non stampare i messaggi del solutore numerico option solver cplex;
option solver_msg 0;
# leggi modello e dati model tsp.mod;
data tsp.dat;
let numerocicli := 0;
# strutture dati per l’algoritmo param nodosuccessore{V} >= 0, integer;
param nodocorrente >= 0, integer;
# rendi simmetrica la matrice delle distanze for {i in V, j in V : i > j} {
let d[i,j] := d[j,i];
}
# algoritmo: risolvi il modello senza vincoli di rottura
# dei sottocicli, trova un sottociclo, aggiungi il vincolo
# corrispondente, e quando non esistono piu‘ sottocicli propri, esci
param termination binary;
let termination := 0;
repeat while (termination = 0) {
# risolvi il problema solve;
let numerocicli := numerocicli + 1;
# trova i successori di ogni nodo for {i in V} {
let nodosuccessore[i] := sum{j in V : j != i} j * x[i,j];
}
# trova un sottociclo let nodocorrente := 1;
let ciclo[numerocicli] := {};
repeat {
let ciclo[numerocicli] := ciclo[numerocicli] union {nodocorrente};
let nodocorrente := nodosuccessore[nodocorrente];
} until (nodocorrente = 1);
# stampa il sottociclo che vogliamo rompere printf "ciclo: (";
for {i in ciclo[numerocicli]} { printf "%d, ", i ;
}
printf "1)\n";
# verifica se si puo‘ terminare
if (card(ciclo[numerocicli]) >= n) then {
# se il sottociclo include tutti i nodi e‘ Hamiltoniano, esci let termination := 1;
} }
printf "costo del ciclo hamiltoniano minimo: %d\n", costociclo;
Soluzione numerica
ciclo: (1, 3, 5, 1)
ciclo: (1, 6, 2, 7, 4, 3, 5, 1)
costo del ciclo hamiltoniano minimo: 153
Approfondimento: Soluzione Euristica
Per la soluzione euristica, si consideri l’euristica
32-approssimata
1per il TSP metri- co (cio`e la cui matrice delle distanze rispetta la disuguaglianza triangolare) ideata da Christofides. L’euristica costruisce un ciclo Hamiltoniano (o tour) nel modo seguente.
1. Si costruisce un albero di supporto di costo minimo T nel grafo G.
2. Si costruisce un matching M di costo minimo tra i vertici del grafo che hanno cardinalit`a dispari in T .
3. Si forma un ciclo Euleriano che consiste dell’unione di T e M (l’unione `e un ciclo Euleriano perch´e per costruzione ogni nodo ha un numero pari di lati adiacenti).
4. Per ogni vertice v tale che |δ(v)|∩(T ∪M ) > 2 (ovvero per ogni v da cui si dipartono pi` u di 2 lati di T e M ), si “contraggono” tutte le coppie di lati adiacenti a v tranne una. L’operazione di contrazione di una coppia di lati {u, v}, {v, w} consiste nel sostituire questi lati con il lato {u, w} (l’operazione `e sempre possibile perch´e il grafo `e completo). Effettuando quest’operazione per tutte le coppie di lati adiacenti a v tranne una, si rispettano i vincoli di “predecessore” e “successore”, perch´e v a quel punto avr`a esattamente 2 lati adiacenti.
Si dimostra in modo piuttosto semplice che l’euristica di Christofides `e
32-approssimata.
Sia ¯ c il costo del tour prodotto dall’euristica di Christofides, c
∗il costo del tour ottimale, e c(F ) = P
(i,j)∈F
d
ijil costo di un insieme di archi F . Ogni tour, compreso quello ottimale,
`e un albero unito a un lato; perci`o c(T ) ≤ c
∗. D’altro canto, ogni tour `e anche un 2- matching (ogni vertice `e assegnato al proprio successore e al proprio predecessore), quindi 2c(M ) ≤ c
∗. Si ha perci`o che c(T ∪ M ) ≤ c(T ) + c(M ) ≤ c
∗+
12c
∗. Per la disuguaglianza triangolare, ¯ c ≤ c(T ∪ M ), e quindi ¯ c ≤
32c
∗, come volevasi dimostrare.
Applichiamo ora l’euristica di Christofides all’istanza in questione. Le figure sotto rappresentano: il grafo originale, l’albero di supporto di costo minimo, il matching di costo minimo tra vertici di stella con cardinalit`a dispari, e l’unione dei due a formare un ciclo Euleriano. Si noti tuttavia che in questa particolare istanza tutti i nodi hanno gi`a grado 2, quindi il ciclo `e gi`a Hamiltoniano. Il costo del ciclo ottenuto con quest’euristica
`e 153, e quindi in questo caso l’euristica trova un ciclo Hamiltoniano di costo minimo.
1
Un algoritmo che risolve un problema di minimizzazione ` e k-approssimato se produce una soluzione
con costo ¯ f tale che ¯ f ≤ kf
∗, dove f
∗` e la soluzione ottima.
original graph 0
1 0 / 86
2 1 / 49
3 2 / 57
4
3 / 31
5 4 / 69
6 5 / 50
6 / 68 7 / 79
8 / 93
9 / 24
10 / 5 11 / 16
12 / 7 13 / 72
14 / 67
15 / 90 16 / 69
17 / 1
18 / 86 19 / 59 20 / 81
Figure 1: Il grafo originale.
sptree cost = 84 0
1 0 / 86
2 1 / 49
3 2 / 57
4
3 / 31
5 4 / 69
6 5 / 50
6 / 68 7 / 79
8 / 93
9 / 24
10 / 5 11 / 16
12 / 7 13 / 72
14 / 67
15 / 90 16 / 69
17 / 1
18 / 86 19 / 59 20 / 81
Figure 2: L’albero di costo minimo.
matching cost: 69 0
1 0 / 86
2 1 / 49
3 2 / 57
4
3 / 31
5 4 / 69
6 5 / 50
6 / 68 7 / 79
8 / 93
9 / 24
10 / 5 11 / 16
12 / 7 13 / 72
14 / 67
15 / 90 16 / 69
17 / 1
18 / 86 19 / 59 20 / 81
Figure 3: Il matching di costo minimo tra vertici di grado dispari.
tour cost: 153 0
1 0 / 86
2 1 / 49
3 2 / 57
4
3 / 31
5 4 / 69
6 5 / 50
6 / 68 7 / 79
8 / 93
9 / 24
10 / 5 11 / 16
12 / 7 13 / 72
14 / 67
15 / 90 16 / 69
17 / 1
18 / 86 19 / 59 20 / 81
Figure 4: Unione di albero e matching (soluzione approssimata).
optimal tour cost: 153 0
1 0 / 86
2 1 / 49
3 2 / 57
4
3 / 31
5 4 / 69
6 5 / 50
6 / 68 7 / 79
8 / 93
9 / 24
10 / 5 11 / 16
12 / 7 13 / 72
14 / 67
15 / 90 16 / 69
17 / 1
18 / 86 19 / 59 20 / 81
