Restriction de l'espace de recherche

Objectif de la restriction

L'objectif de la restriction est de simplifier l'espace de recherche. Elle restreint le graphe de départ en un sous-ensemble d'arêtes candidates. Pour ce faire, nous définissons une mesure sur les arêtes permettant de les classer par rang.

Restriction par la distance

La restriction d'un graphe aux plus proches voisins n'est pas une bonne solution. Pour certains problèmes, il faudrait garder plus de $20$ voisins pour obtenir un sous-graphe contenant la tournée optimale. On peut appliquer une autre méthode qui consiste à définir une nouvelle mesure sur l'ensemble des arêtes : l'$\alpha$-sensibilité.

Restriction grâce à l'arbre couvrant de poids minimal

Définitions

La majorité des arêtes d'un arbre couvrant de poids minimal appartiennent à la tournée optimale. Nous allons donc classer les arêtes en nous servant de cette propriété. Pour aborder la notion d'$\alpha$-sensibilité d'une arête, nous avons besoin de quelques définitions.

1. Arbre couvrant de poids minimal (ACM) Un ACM est un graphe connexe respectant les conditions suivantes :
   • il n'a pas de cycle²
   • si $n$ est le nombre de sommets du graphe alors l'ACM a $n-1$ arêtes
   • la somme des poids de l'ensemble de ses arêtes est minimale
   Il existe un algorithme³ de complexité $O(n^2)$ pour trouver un ACM à partir d'un graphe composé de $n$ sommets.
2. 1-arbre Un 1-arbre de racine $R$ pour un graphe $G=(N,E)$ est un arbre couvrant l'ensemble des sommets $N\backslash\{R\}$ auquel on ajoute $2$ arêtes de $E$ incidentes au sommet $R$. Il est dit minimal si la somme des poids de ses arêtes est minimale.
3. $\alpha$-sensibilité L'$\alpha$-sensibilité d'une arête est la différence ente le coût d'un 1-arbre de poids minimal contenant cette arête et le coût d'un 1-arbre minimal. Il existe un algorithme⁴ de complexité $O(n^2)$ pour calculer les valeurs d'$\alpha$-sensibilité des arêtes d'un graphe de $n$ sommets.

Restriction par l'$\alpha$-sensibilité

Entre $70\%$ et $80\%$ des arêtes d'un 1-arbre minimal sont contenues dans une tournée optimale. Il est donc assez naturel de l'utiliser pour une mesure heuristique de proximité. Les arêtes dont l'$\alpha$-sensibilité dépasse une limite fixée peuvent être éliminées du graphe. On montre ⁵ que la restriction par l'$\alpha$-sensibilité est plus efficace que la restriction par les distances.

Amélioration par la relaxation Lagrangienne

L'$\alpha$-mesure peut être améliorée en utilisant une simple transformation de la matrice de coût. Cette transformation est basée sur les observations suivantes :

• une tournée optimale est un 1-arbre minimal où chaque sommet est de degré $2$
• une tournée est une borne inférieure du coût de cette tournée (se déduit de l'observation précédente)
• le rajout de pénalités complémentaires dans les sommets ne change pas la tournée optimale (puisque le coût de chaque tournée augmente de la somme des pénalités) :  si la longueur de chaque arête incidente à un noeud $i$ augmente d'une quantité $\pi_i$, la transformation préserve le TSP invariant. Ainsi, si la matrice $C=(c_{ij}$) de coût entre les villes est transformée en $D=(d_{ij})$, où $d_{ij} = c_{ij} + \pi_i + \pi_j$, alors une tournée optimale pour $D$ l'est aussi pour $C$. La longueur de la tournée étant augmentée de $2\sum\pi_i$.
• le rajout de pénalités pertube le 1-arbre minimal (c'est ce qui est exploité)

Le coût du 1-arbre minimal étant une borne inférieure du coût de la tournée optimale, la restriction par $\alpha$-sensibilité peut être améliorée en maximisant cette borne. Le problème de maximisation de cette borne par la pénalisation des sommets est décrit par Held et Karp⁶. C'est un problème de maximisation concave. La méthode des sous-gradient peut être appliquée. Keld Helsgaun l'a implanté. D'après ses propres expériences, le maximum trouvé est dans le pire des cas $1\%$ en dessous de l'optimum.

Efficacité de la restriction

K. Helsgaun donne le tableau 3 pour montrer la supériorité de la nouvelle mesure sur la mesure initiale. Chacune d'elles permet de classer les arêtes dans l'ordre ascendant. Celà définit le rang d'une arête. Le tableau 3 montre la proportion d'arêtes de la tournée optimale ayant un certain rang pour différentes mesures. Exemple : $43.7\%$ des arêtes de la tournée optimale connectent un sommet à son $1^{er}$ voisin le plus proche et $24.5\%$ à son $2^{eme}$ voisin le plus proche. Le rang moyen correspond à la moyenne pondérée des rangs par leur proportion dans une tournée optimale. La valeur moyenne minimale et idéale vaut $1.5$ : chaque arête de la tournée optimale est la $1^{ere}$ ou la $2^{eme}$ meilleure arête candidate.Plus la moyenne des rangs est grande, plus le sous-graphe des meilleurs candidats est dense. Selon Helsgaun, pour les problèmes de TSPlib la tournée optimale est dans le sous-graphe des $5$ meilleurs candidats ⁷ en utilisant l'amélioration de la nouvelle mesure d'$\alpha$-sensibilité.

Tableau 3: Statistiques pour le problème att532 de TSPlib

Rang	C	$\alpha$	$\alpha$ amélioré	idéal
1	43,7	43,7	47,0	50
2	24,5	31,2	39,5	50
3	14,4	13,0	9,7
4	7,3	6,4	2,3
5	3,3	2,5	0,9
6	2,9	1,4	0,1
7	1,1	0,4	0,3
8	0,7	0,7	0,2
9	0,7	0,2
10	0,3	0,1
11	0,2	0,3
12
13
14		0,1
15
16
17
18
19	0,1
20
21
22	0,1
Rang moyen	2,4	2,1	1,7	1,5