Devoir maison 2: Clustering

On considère l’île de Man. Le fichier distribué en TD décrit son réseau routier sous forme de graphe orienté, dont les sommets sont les intersections et les arcs des routes entre deux intersections, pondérés par le temps de trajet. Pour ce devoir maison, nous allons supposer que les routes sont navigable dans les deux sens. Pour simplifier les données on se restreint aux sommets dont les coordonnées GPS sont entre 54.0790 et 54.1549 pour la longitude et entre -5, -4.7364 pour la latitude. Ainsi le graphe est composé de 345 sommets. Ce graphe définit une métrique sur l’espace des sommets $V$ : la distance $d_{uv}$ entre deux sommets $u,v$ est la longueur du plus court chemin entre les deux. Avec le filtrage des points GPS ci-dessus, le graphe n’est pas connexe, aussi on définit à 1E9 la distance entre des sommets de differentes composantes connexes. Ces distances peuvent être calculées en quelques minutes en Python avec l’algorithme de Bellman-Ford (Floyd-Warshall est beaucoup plus lent pour ce graphe éparse). Pour vous faciliter la tâche, les distances ont été calculées et mis à votre disposition ici.

Dans le problème k-médiane, il est demandé de produire une liste de k sommets $c_1,\ldots,c_k$, qui minimise \[ ​ \sum_{v\in V} \min_{i} d_{c_i, v}. \]

Dans le problème k-moyennes, il est demandé de produire une liste de k sommets $c_1,\ldots,c_k$, qui minimise \[ ​ \sum_{v\in V} \min{i} d_{c_i, v}^2. \]

Dans le problème k-centre, il est demandé de produire une liste de k sommets $c_1,\ldots,c_k$, qui minimise \[ ​ \max_{v\in V} \min{i} d_{c_i, v}. \]

Ce qui est demandé

Pour $k=6$, calculez des solutions optimaux pour chacun de problèmes. Utilisez le solveur de programmation linéaire à variables entières utilisé en TD pour cela. Comparez les trois soutions.

Déposez

Si les performances sont trop faibles, signalez le rapidement et on choisira un graphe d’entrée plus petit. Envoyez un document décrivant votre approche et les résultats des expériences, ainsi que vos codes dans fichier zip avant le 22 janvier 2019.