Projet d’Algorithmique appliquée (2021-2022)

An english version of the project is available here!

Présentation générale

Dans ce projet, l’objectif est de placer astucieusement des centres de vaccination dans une ville de telle sorte que toute personne se trouve à proximité d’un centre de vaccination. Ce projet se déroulera en plusieurs étapes :

modélisation du problème ;
implémentation d’algorithmes résolvant le problème : brute force, algorithmes basés sur de la programmation dynamique, algorithmes progressifs, d’approximation etc. ;
test de vos algorithmes sur différentes instances ;
extensions possibles.

Concernant l’organisation :

groupes de 3 ou 4 étudiants ;
langages de programmation autorisés : C, C++, Java ou Python ;
la version finale devra être rendue avant les vacances de Noël, et des soutenances auront lieu en janvier ;
possibles rendus intermédiaires (plus de détails à venir…).

Format des fichiers d’entrée

Deux principaux formats doivent pouvoir être pris en compte comme fichier d’entée :

une image stockée au format PPM ;
sous forme de graphe, que l’on peut représenter par exemple sous forme de liste d’adjacence.

Le format PPM

Description

Le format PPM (pour Portable Pixmap) est un moyen très simple de décrire une image sous forme textuelle. Dans notre cas, il s’agira de fichiers ASCII de ce format (voir Wikipedia) :

P3 # fichier PPM ASCII sous format RGB
3 2 # l'image contient 3 colonnes et 2 lignes
255 # chaque composante R, G et B est représentée par un entier entre 0 et 255
255  0    0     0  255  0       0   0  255 # première ligne 
0   255   0     0   0  255     255  0   0  # deuxième ligne

Le fichier de configuration associé

En plus du fichier au format PPM, un fichier de configuration config.txt permet d’indiquer :

le niveau d’échelle souhaité ;
pour chaque couleur (i.e., chaque triplet (R,G,B)) présente dans le fichier PPM, on associe un indice.

Le niveau d’échelle scale est un nombre entier supérieur ou égal à 1 qui permet de partionner l’image en carrés disjoints de scale * scale pixels. L’objectif est de réduire la taille de vos instances (à vous de voir comment !), qui risque d’être trop grosses selon la taille de l’image choisie.

Enfin, associer à chaque couleur présente dans l’image un indice permet de représenter le coût potentiel pour traverser cette zone (i.e. ce pixel). Par exemple, pour se déplacer en (x+1,y) depuis (x,y) en se déplaçant d’un pixel vers la droite, le coût est donné par coût[(x,y)] + coût[(x+1,y)]. On peut voir ceci comme le poids de l’arête (x,y) - (x+1,y). Enfin, notons qu’il n’est pas toujours possible de traverser un pixel (par exemple s’il se situe sur de l’eau) : nous utiliserons dans ce cas l’indice 0 pour la couleur correspondante.

Si on reprend l’exemple du fichier PPM ci-dessus, on s’aperçoit que celui-ci contient seulement 3 couleurs différentes :

(0, 0, 255) : bleu ;
(0, 255, 0) : vert ;
(255, 0 ,0) : rouge.

Un exemple de fichier de configuration config.txt associé à cette image peut être par exemple :

1 # échelle 1, i.e., on ne modifie pas l'image
0 255 0 0   # l'indice de la couleur (255,0,0) est 0
1  0 255 0  # l'indice de la couleur verte est 1
3  0  0 255

Dans cet exemple, on indique notamment qu’il n’est pas possible de se déplacer sur un pixel de couleur rouge.

Un exemple concret

Voici un exemple concret d’image que vous devez pouvoir manipuler :

Image de Paris

Le fichier PPM associé à cette image peut être téléchargé ici. Si on ouvre ce fichier, on s’aperçoit notamment que l’image est de taille 1727*764 et que chaque ligne du fichier ne contient qu’un seul triplet (R,G,B), et non autant de triplets qu’il n’y a de colonnes (i.e., la largeur de l’image). Il s’agit d’un stockage correspondant à un row-major order (voir Wikipedia) : les 1727 premiers triplets représentent la première ligne, les triplets 1728 à 3454 la deuxième ligne et ainsi de suite. Cette image contient sept couleurs différentes :

(0,0,0) : noir ;
(0,0,255) : bleu ;
(0,255,0) : vert ;
(255,0,0) : rouge ;
(255,0,255) : magenta ;
(255,255,0) : jaune ;
(255,255,255) : blanc.

On peut ainsi remarquer que la couleur noire représente les zones d’eau (comme la Seine), la couleur magenta les routes principales etc. On peut ainsi associer le fichier de configuration suivant :

1 # échelle 1, i.e., on ne modifie pas l'image
0   0   0   0   # la couleur noire a un indice de 0
1  255  0  255  
3  255 255 255
4  255  0   0
7   0   0  255
10  0  255  0
17 255 255  0

Création d’autres images PPM

Vous pouvez facilement créer d’autres instances de votre choix. Pour cela, vous devez :

aller sur uMap puis cliquer sur “Créer une carte” ;
changer le fond de carte (menu vertical à droite) et choisir “OSM Watercolor” ;
faire une capture d’écran de la zone souhaitée dans un fichier file.png.

Pour exporter l’image en PPM :

ouvrir file.png avec GIMP ;
Fichier > Exporter sous > file.ppm > Exporter ;
choisir ASCII.

Il vous faudra ensuite lancer la commande suivante depuis un terminal :

$ awk '{ ++x; if(x<=3) print $0; else { l1=$0; getline; l2=$0; getline; print l1 " " l2 " " $0; }}' file.ppm > res.ppm

Ceci permet de récupérer le fichier PPM final dans un fichier res.ppm. Ici,, le x<=3 signifie que la couleur du pixel de coordonnées (0,0) est sur la ligne 4 du fichier file.ppm. Attention, Gimp a tendance à rajouter une ligne de commentaire (ligne commençant par le caractère #). Si c’est le cas, supprimez les lignes de commentaires avant de lancer la commande.

On peut également modifier l’image et réduire le nombre de couleurs sous GIMP :

Image > Mode > Couleurs indexées ;
Générer une palette optimale et choisir le nombre maximal de couleurs.

Enfin, on peut pour chacune des couleurs indexées choisir la valeur (R,G,B) :

Fenêtres > Fenêtres ancrables > Palette des couleurs indexées ;
Cliquer sur la couleur en question ;
Dans Notation HTML, écrire la couleur désirée en hexadécimal (000000 à ffffff).

Pensez ensuite à bien exporter de nouveau l’image au format PPM et à lancer la commande awk.

Le format graphe

Votre programme doit également pouvoir lire des graphes en entrée. Ceux-ci sont représentés sous forme de liste d’adjacence comme ceci :

0: 3 5 7 
1: 2 3
2: 1 4 ...
...
n-1: ...

Pour générer des exemples de graphes, vous pourrez utiliser gengraph.c dont la documentation est disponible ici. Pour compiler gengraph sous Linux :

$ gcc gengraph.c -lm -lbsd -o gengraph

ou sous MacOS :

$ gcc gengraph.c -o gengraph

Vous pouvez par exemple générer une grille de taille 3x3 en faisant :

$ ./gengraph mesh 3 3 -format list
0: 1 3
1: 0 2 4
2: 1 5
3: 0 4 6
4: 1 3 5 7
5: 2 4 8
6: 3 7
7: 4 6 8
8: 5 7

Vous pouvez aussi tester ./gengraph mesh 3 3 -format list -header qui vous donnera des informations complémentaires, et ./gengraph -list pour la liste des 207 graphes que vous pouvez visualiser avec, par exemple:

$ gengraph mesh 10 10 -dele 0.2 -visu; open g.pdf

L’option dele 0.2 permet de supprimer chaque arête du graphe généré avec probabilité 0.2. L’option delv p fonctionne de façon similaire.

On considérera alors que les coûts sont tous égaux (à 1 par exemple) pour tous les sommets du graphe. Il n’y a alors pas de fichier de configuration associé.

Énoncé plus formel

Ainsi, on voit bien que l’on peut représenter chaque instance sous forme de graphe. Il vous appartient de modéliser le problème comme un problème de graphe. La problématique qui nous intéresse est donc la suivante :

Étant donné un graphe dont les sommets sont pondérés, et un nombre réel positif r, on souhaite placer le plus petit nombre de centres de vaccinations de telle sorte que chaque personne (peu importe sa localisation géographique) soit à une distance au plus r d’un centre vaccination (à vous de définir la notion de distance).

Supposons maintenant que l’on dispose d’un budget limité permettant de construire au plus k centres. La question est donc ce savoir où placer ces k centres de façon à minimiser la distance maximale d’un point (i.e. un pixel de l’image) à un centre.

Premier rendu

On vous demande un petit rapport (fichier texte ou PDF) expliquant :

la construction du graphe : quels sont les sommets ? les arêtes ?
l’énoncé formel du problème : quelle est une instance type (entrée, question) ? -> Vous devez définir toutes les notions utilisées (à quoi correspond une distance par exemple ?)
expliquez et justifiez vos choix (algorithmiques et de programmation) en quelques mots ! Vous pouvez insérer un peu de code si nécessaire.
comment vous passez d’une solution de votre problème de graphe aux coordonnées (de l’image) où placer les centres de vaccination ?
toute information jugée utile est la bienvenue.

Date limite : vendredi 1 octobre

Énoncés formels

Comme nous l’avons vu, nous allons concevoir des algorithmes permettant de résoudre un problème de graphe, à savoir le problème Ensemble Dominant. Pour cela, on dispose d’un graphe pondéré G = (V, E), où V représente l’ensemble des sommets de G, et E l’ensemble de ses arêtes. Chaque sommet u ∈ V possède un poids ω(u) ∈ ℕ^*. Pour chaque arête e = (u, v) ∈ E, on définit alors ω(e) = ω(u) + ω(v).

Le coût d’un chemin C (noté coût[C]) est la somme des poids des arêtes de C. La distance entre deux sommets u et v (notée dist(u, v)) est le coût d’un plus court chemin de u à v, c’est-à-dire le coût d’un chemin de u à v de poids minimum. On fixe dist(u, u) = 0.

Étant un nombre (réel ou entier) r, un ensemble r-dominant de G est un sous-ensemble de sommets S ⊆ V tel que tout sommet de G est à distance au plus r d’un sommet de S, i.e. ∀u ∈ V, ∃v ∈ S t.q. dist(u, v) ≤ r.

Ainsi, le premier problème étudiant est le suivant :

Entrée : un graphe G = (V, E) avec un poids sur chaque arête, un nombre r

Question : quel est le plus petit entier k tel que G possède un ensemble r-dominant de taille ≤ k ?

Le deuxième problème est le suivant :

Entrée : un graphe G = (V, E) avec un poids sur chaque arête, un nombre entier k

On veut : le plus petit r tel qu’il existe un ensemble r-dominant de taille au plus k

Notons qu’on peut résoudre la deuxième question à l’aide de la première. L’idée est de fixer r et de trouver la taille d’un plus petit ensemble r-dominant de G. Par dichotomie sur r (pour aller plus vite) en fonction de la valeur renvoyée, on pourra ainsi répondre à la question. En effet, notons ℓ le rayon de G. On fixe d’abord r = ℓ. On sait alors qu’il existe un ensemble r-dominant de taille 1. Puis on fixe maintenant r = ℓ/2. S’il existe un ensemble r-dominant de taille ≤ k, on recommence avec r = ℓ/4 et ainsi de suite. Sinon, on essaie entre 3/4ℓ et ℓ (la valeur au milieu entre ℓ/2 et ℓ) et ainsi de suite…

Algorithme exact

Dans un premier temps, on souhaite concevoir et implémenter un algorithme exact pour la première question, c’est-à-dire calculer la taille d’un plus petit ensemble r-dominant (avec r fixé). Vous pouvez utiliser un algorithme brute-force, et/ou utiliser un solveur (SAT, PLNE)…

Algorithmes exacts pour Ensemble Dominant

Dans cette section, nous nous intéressons à des algorithmes exacts permettant de résoudre le problème Ensemble Dominant, qui correspond à chercher un ensemble 1-dominant dans un graphe où toutes les arêtes ont un poids de un. Notons que l’on peut facilement transformer une instance (G=(V,E), r) du problème Ensemble r-Dominant en une instance (G’=(V’,E’)) de Ensemble Dominant, où G′ est un graphe non pondéré tel que :

V’ = V ;
uv ∈ E’ ⇔ dist_G(u,v) ≤ r.

Algorithme de type Branch-and-Bound

Une première possibilité est d’implémenter un algorithme de type Branch and bound. L’idée est de remarquer que S ⊆ V est un ensemble dominant de G si et seulement si ∀u ∈ V, N[u] ∩ V ≠ ∅, où N[u] représente le voisinage fermé de u, c’est-à-dire l’ensemble contenant u et tous ses voisins. On peut alors imaginer un algorithme récursif qui va tester étant donné un sommet u toutes les façons possibles de dominer u, c’est-à-dire qui va brancher sur chaque sommet de N[u]. Cela créer un arbre de hauteur au plus k (car on ne s’intéresse qu’à des ensembles S de taille ≤ k), mais de largeur non bornée. Pour cela, on sélectionne un sommet de plus petit degré. Cela donne un algorithme comme celui-ci :

ensemble_dominant(graphe G, dominant partiel S, entier k)
    si k = 0 :
        tester si S est un dominant 
    sinon :
        u <- sommet de degré min parmi les sommets non dominés par S
        pour tout v dans N[u] :
            ensemble_dominant(G, S U {v}, k-1)

Avec comme appel initial ensemble_dominant(G, ∅, k).

Deuxième rendu

On vous demande un petit rapport (fichier texte ou PDF) expliquant :

les algorithmes exacts que vous avez implémentés (brute force, branch-and-bound, utilisation de solveur(s)) ;
vos choix algorithmiques et de programmation (utilisation de telle ou telle structure de données) ;
vos optimisations (si vous en avez) ;
des tests sur vos algorithmes (marchent-ils ?)
des benchmarks pour les évaluer (temps de calcul, nombre de sommets maximum) et éventuellement les comparer (si vous avez implémenté plusieurs algorithmes).

Date limite : vendredi 19 novembre

Algorithme de programmation dynamique

Dans cette section, nous présentons un algorithme de programmation dynamique basé sur un article disponible ici.

On rappelle qu’étant donné un graphe G = (V, E), un ensemble indépendant (ou stable) est un sous-ensemble de sommets I ⊆ V tel que pour toute paire de sommets u, v ∈ I, uv ∉ E. Le problème qui consiste à déterminer la taille d’un plus grand ensemble indépendant de G est NP-complet. En revanche, on peut trouver très facilement un ensemble indépendant maximal, à l’aide d’un algorithme glouton par exemple.

Soit I = {v₁, v₂, …, v_k} un ensemble indépendant de G, et notons J = V \ I. Maintenant, l’algorithme se déroule en deux étapes :

on pré-calcule pour chaque sous-ensemble X ⊆ J un sous-ensemble de plus petite cardinalité D_x ⊆ I qui domine X ;
on calcule pour chaque sous-ensemble D_J ⊆ J un ensemble de plus petite taille dominant G et contenant D_J.

Première étape

Pour chaque sous-ensemble X ⊆ J et pour chaque entier ℓ, 1 ≤ ℓ ≤ k, on note par Opt(X, ℓ) un ensemble D_X, ℓ de cardinalité minimum (s’il existe) tel que :

D_X, ℓ ⊆ {v₁, v₂, …, v_ℓ} ;
X ⊆ N[D_X, ℓ].

Autrement dit, étant donné un sous-ensemble de sommets X de J et un entier ℓ compris entre 1 et k (avec k = |I|), on cherche un sous-ensemble D_X, ℓ qui n’utilise que les ℓ premiers sommets de I (mais pas nécessairement tous), et qui domine X. Nous allons donc calculer dans une table toutes les valeurs D_X, ℓ à l’aide de la programmation dynamique, et par valeurs croissantes de ℓ.

Figure 1 : Opt[X,4] = \{v_1, v_2, v_4\} avec Opt[X,4] \subseteq \{v_1, v_2, v_3, v_4\} et Opt[X,4] qui domine X. — Figure 1 : Opt[X, 4] = {v₁, v₂, v₄} avec Opt[X, 4] ⊆ {v₁, v₂, v₃, v₄} et Opt[X, 4] qui domine X.

Sur la figure 1, on observe que {v₁, v₂, v₄} domine bien X et utilise uniquement des sommets de {v₁, v₂, v₃, v₄}. On peut vérifier qu’il n’existe pas d’ensemble D ⊆ {v₁, v₂, v₃, v₄} tel que D domine X et |D|< |Opt[X, 4]| = |{v₁, v₂, v₄}| = 3.

Certaines valeurs de cette table sont très faciles à calculer, et représentent les “cas de base” :

∀1 ≤ ℓ ≤ k, Opt[∅, ℓ] = ∅ car ici X = ∅ et nous n’avons donc aucun sommet à dominer ;
∀X ⊆ J, Opt[X, 1] = {v₁} si v₁ domine X, {∞} sinon. En effet, il n’existe qu’un seul ensemble D_X, 1 qui satisfait la condition 1 : il s’agit du singleton {v₁}. Il reste donc à déterminer s’il respecte la condition 2 (de domination). Si ce n’est pas le cas, on utilise la valeur sentinelle {∞} qui indique qu’un tel ensemble n’existe pas.

Figure 2 : Opt[X,1] = \{v_1\} car v_1 domine X et Opt[X',1] = \{\infty\} car v_1 n’est pas adjacent à tous les sommets de X'. — Figure 2 : Opt[X, 1] = {v₁} car v₁ domine X et Opt[X′, 1] = {∞} car v₁ n’est pas adjacent à tous les sommets de X′.

Nous pouvons maintenant calculer Opt[X, ℓ] pour tout sous-ensemble de J non vide et pour tout 2 ≤ ℓ ≤ k à l’aide de la récurrence suivante :

Opt[X, ℓ] = {le plus petit ensemble parmi Opt[X, ℓ − 1] et {v_ℓ} ∪ Opt[X \ N[v_ℓ], ℓ − 1]}.

Figure 3 : Opt[X,5] = Opt[X,4] mais Opt[X',5] = \{v_5\} \cup Opt[X'',4] avec X'' = X' \setminus N[v_5]. — Figure 3 : Opt[X, 5] = Opt[X, 4] mais Opt[X′, 5] = {v₅} ∪ Opt[X″, 4] avec X″ = X′ \ N[v₅].

En effet, dans un plus petit ensemble dominant D_X, ℓ ⊆ {v₁, v₂, …, v_ℓ} de X :

soit v_ℓ ∉ D_X, ℓ, et dans ce cas là on lit dans la table Opt[X, ℓ − 1] (on cherche un plus petit dominant de X qui n’utilise que les ℓ − 1 premiers sommets de I, s’il existe);
soit v_ℓ ∈ D_X, ℓ auquel cas on cherche dans la table un plus petit dominant de X \ N[v_ℓ] (i.e., X privé de tous les sommets dominés par v_ℓ) n’utilisant que des sommets de {v₁, v₂, …, v_{ℓ − 1}}. En effet, comme v_ℓ ∈ D_X, ℓ, on cherche simplement un dominant de X \ N[v_ℓ] dans la table.

Notons que nous avons 2^{|V| − k} sous-ensembles X ⊆ J et k valeurs à calculer pour chaque X, ce qui donne une table de taille k × 2^{|V| − k}.

Deuxième étape

Dans cette étape, étant donné un ensemble D_J ⊆ J, nous souhaitons calculer un ensemble dominant D = D_J ∪ D_I de G de taille minimum avec D_I ⊆ I. L’ensemble D_I se décompose en deux ensembles D_I¹ et D_I². D_I¹ = I \ N(D_j), c’est-à-dire D_I¹ contient tous les sommets de I qui ne sont pas dominés par D_J. Comme V = I ∪ J et que I est un ensemble indépendant, nous sommes obligés de tous les prendre dans D afin de les dominer. Notons que les sommets de D_I¹ dominent certains sommets de J, que l’on note N(D_I¹). Ainsi, D_I¹ ∪ D_J domine tous les sommets de I. Il ne reste donc plus qu’à dominer les sommets de J \ (N[D_J] ∪ N(D_I¹)). Pour cela, on fixe D_I²= Opt[J \ (N[D_J] ∪ N(D_I¹)), k].

Figure 4 : Ensemble dominant D = D_J \cup D^1_I \cup D^2_I d’un graphe G=(V,E) avec V = I \cup J où I est un stable de G. — Figure 4 : Ensemble dominant D = D_J ∪ D_I¹ ∪ D_I² d’un graphe G = (V, E) avec V = I ∪ J où I est un stable de G.

L’ensemble D ainsi calculé correspond donc à la plus petite taille d’un ensemble dominant contenant D_J. En énumérant tous les sous-ensembles D_J ⊆ J, on peut donc calculer la taille d’un plus petit ensemble dominant de G (ne pas oublier le cas D_J = ∅ !).

L’algorithme final

L’algorithme final commence par calculer un ensemble indépendant maximal I du graphe G = (V, E) à l’aide d’un algorithme glouton. Soit k = 0.2271 × |V|. Si |I| ≥ k|, nous exécutons les étapes 1 et 2. Sinon, |I| < k et donc la taille d’un plus petit ensemble dominant de G est strictement inférieure à k (puisque pour tout graphe, tout ensemble indépendant maximal est également un ensemble dominant). Nous pouvons alors générer tous les sous-ensembles de sommets de taille au plus k pour trouver un ensemble dominant de plus petite taille.

Troisième rendu

On vous demande un petit rapport (fichier texte ou PDF) expliquant :

l’implémentation de l’algorithme de programmation dynamique avec vos choix algorithmiques et de programmation (utilisation de telle ou telle structure de données) ;
vos optimisations (si vous en avez) ;
des tests pour tester la validité de celui-ci (comparaison du résultat avec celui obtenu grâce à votre algorithme brute-force) ;
des benchmarks pour l’évaluer (temps de calcul, nombre de sommets maximum) et éventuellement le comparer à vos autres algorithmes exacts) ;
les limites de votre algorithme.

Date limite : vendredi 10 décembre

Algorithme progressif

Nous vous demandons d’implémenter l’algorithme progressif présenté en cours (voir la section 2.12 des notes de cours ici).

Travail en autonomie

La dernière partie de ce projet est libre. Vous pouvez par exemple décider :

de concevoir et implémenter vos propres algorithmes,
d’implémenter des algorithmes trouvés dans la littérature ou sur internet,
optimiser vos algorithmes déjà implémentés,
essayer de produire des solutions pour les images PPM (qui génèrent de très gros graphes).

À chaque fois, il vous est demandé de tester expérimentalement vos algorithmes (réaliser des benchmarks), d’expliquer le gain en temps et/ou mémoire si vous avez optimisé votre code etc.

Soutenances

Il vous est demandé d’envoyer votre rapport final (format PDF) d’ici le 27 janvier. Les soutenances auront lieu le 3 février (CREMI, salle 202) et dureront 20-25 minutes par groupe. Voici les horaires de passage pour chaque groupe :

9h : Sylvain Lichau et Luis Lopes Marques,
9h25 : Hugo Bergon, Théo Hollender et Pierre-Antoine Rouby,
9h50 : Louis Cantin, Lucas Declercq et Charles Silari,
10h15 : Eliot Coquilleau, Louis Duplantier, Kirsan Geoffroy et Mathis Sauvanet,
10h40 : Raphaël Comet, Jean Crabos, Amaury Jacques et Hugo Marchand,
11h05 : Simon Bullot, Hussam Eddin Einieh, Roxane Flores et Guillaume Mannone.

Nous vous demandons d’entrer discrètement dans la salle 10 minutes avant votre horaire et de vous installer sur un ordinateur afin d’éviter toute perte de temps. Vous devrez présenter rapidement ce que vous avez fait, puis nous vous poserons des questions à propos de votre projet. Vous pouvez utiliser des slides, mais ce n’est pas obligatoire.