Problema del TSP

uni
TSP = traveling salesman problem = problema del commesso viaggiatore
Dati dei nodi collegati da archi, con ogni arco con relativo costo:
Trovare il cammino di costo minimo che includa tutti i nodi una ed una sola volta, detto Ciclo Hamiltoniano.
Questo problema su $n$ nodi ha $n!$ soluzioni ammissibili.

Modello Asimmetrico

$N$ nodi
Variabili: $x_{ij}=(arco(i,j)\in ciclo)?1:0$

$$\{\begin{array}{l}\min {\sum }_i{\sum }_j{c}_{ij}\cdot x_{ij}\\ {\sum }_j{x}_{ij}=1\forall i\\ {\sum }_i{x}_{ij}=1\forall j\\ {\sum }_{\begin{array}{c}i\in S\\ j\notin S\end{array}}{x}_{ij}\ge 1\forall S\in N,S\ne \varnothing ,S\ne N\\ x_{ij}\in \{0,1\}\end{array}$$

Modello Simmetrico

Quando la direzione dei legami non importa.
Potremmo usare le tecniche risolutive del TSP Asimmetrico ma come segue possiamo dimezzare le variabili.

$$\{\begin{array}{l}min{\sum }_i{\sum }_{j>i}{c}_{ij}\cdot x_{ij}\\ {\sum }_{i<j}{x}_{ij}+{\sum }_{j<i}{x}_{ji}=2\forall j\\ \\ {\sum }_{\begin{array}{c}i\in S\\ j\notin S\\ i<j\end{array}}{x}_{ij}+{\sum }_{\begin{array}{c}i\notin S\\ j\in S\\ j<i\end{array}}{x}_{ji}\ge 1\forall S\subset N,S\ne \varnothing ,S\ne N\\ x_{ij}\in \{0,1\}\end{array}$$

I Primi si chiamano vincoli di grado, ovvero ogni nodo ha tot legami, grado 2, e sono $n$ vincoli (con $n=|nodi|$). In ogni vincoli ci sono $n-1$ legami.
I secondi si chiamano vincoli di connessione.
Le variabili sono $|x|=\frac{n!}{|S|!(n-|S|)!}$
La matrice $Aeq$ avrà dimensioni $n\times |x|$
La matrice $A$ avrà dimensioni $(2^n-2n-2)\times |x|$ ma in realtà si dimezzano.

Risoluzione

Trovare una $V_I$, trovare una $V_S$, applicare Riduzione del Gap (valido per tutte le PLI).

• $V_I$: Trovare k-Albero tramite Algoritmo di Kruskal.
• $V_S$: Algoritmo del Nodo più vicino.
• Riduzione del gap: Algoritmo di Riduzione del Gap Branch and Bound.