Voyageur de commerce

Comment décider si une modélisation est meilleure qu’une autre? Un critère important est le gap d’intégralité, le rapport entre l’optimum entier et l’optimum fractionnel. On veut ce rapport le plus proche de 1.

On dit que deux modélisation sont équivalents, si les solutions optimal entières sont les mêmes, et la première modélisation est meilleure que la deuxième si tout solution fractionnelle au premier modèle est aussi une solution au deuxième modèle et que cette inclusion est stricte.

Voici trois modélisation pour le problème du voyageur de commerce. Ici $V$ est l’ensemble des sommets et $c$ le coût sur les arcs (disons que le graphe est complet). Ici $n$ représente le nombre de sommets, et les coûts de l’arc $(i,j)$ peut être différent de celui de l’arc $(j,i)$.

Modèle 1 – coupe

$\min \sum_{i j} c_{ij} x_{ij}$ $\forall i: \sum_{j} x_{ij} =1$ $\forall j: \sum_{i} x_{ij} =1$ $\forall U \subseteq V,2 \leqslant | U | \leqslant | V | -2: \sum_{i \in U} \sum_{j \not\in U} x_{ij} \geqslant 1$

Modèle 2 – graphe induit

Remplace le dernier ensemble de contraintes par (pour les mêmes conditions sur $U$

$\forall U: \sum_{i \in U} \sum_{j \in U} x_{ij} \leqslant | U | -1.$

Modèle 3 – potentiel

Ce modèle utilise des variables supplémentaires $( u_{i} )_{i}$ et remplace le dernier ensemble de contraintes par

$\forall i,j,j\neq 1:u_{i} -u_{j} + | V | x_{ij} \leqslant | V | -1.$

L’idée est que $u$ représente un rang du sommet sur le tour, si le sommet $i$ est le $k$-ième sommet sur le tour en partant du sommet $1$ alors on veut que $u_i-u_1=k$.

Modèle 4 - flot

Ce modèle utilise des variables $y_{ij}$ pour chaque arc. L’idée est que le voyageur débute le tour avec $n$ jetons en poche et dépose un jeton dans chaque sommet visité. Alors $y_{i,j}$ est le nombre de jetons en poche au moment de la traversée de l’arc $(i,j)$. Le dernier ensemble de contraintes est remplacé par

$\forall i,j : y_{ij} \leq (n-1) x_{ij}$ $\forall i : \sum_{j} y_{ji} - \sum_j y_{ij} = [\text{ if } i=1 \text{ then } 1-n \text{ else } 1 ]$

Exercice papier (ou tableau)

Comparez ces modèles pour leur ensemble de solutions. Pour les modèles 3 et 4, considérez l’ensemble des solutions projetées sur les variables $( x_{ij} )$. Pourquoi bien qu’ayant un nombre polynomial de contraintes, les deux dernières modélisation pourraient toute fois être moins efficace ?

Exercice machine

Implémentez les modèles en ZIMPL et comparez leur performances sur l’exemple burma14 de la bibliothèque TSPLIB. Trouvez un tours qui visite chacun des 14 points données et qui minimise la distance euclidienne totale entre les points successifs.