Directed Feedback Vertex Set (Projet Programmation L3 MIAGE 2022-2023)
En quelques mots:
Le but de ce projet est de participer à la track heuristic du challenge PACE pour le problème de graphes Directed Feedback Vertex Set en proposant un algorithme pour le résoudre.
Dates
Rendu du projet : 13 février 23h (automatique via Github)
Soutenances : 17 février après-midi (présentations de 5 minutes devant la classe). Possibilités de faire des slides (les mettre sur le git, je ferai un pull avant la présentation).
2 décembre 2022: mise en ligne du sujet
Directed Feedback Vertex Set
Etant donné un graphe orienté, une question basique consiste à déterminer quels sommets supprimer du graphe afin qu’il ne reste plus aucun cycle orienté dans le graphe. Voir Wikipedia.
Dans cet exemple, le graphe de gauche contient 2 cycles. Supprimer le sommet rouge supprimer tous les cycles du graphe.
On se propose de résoudre ce problème dans ce projet, dans le cadre d’un challenge international.
Ce problème est dit difficile à résoudre optimalement (NP-complet). Nous verrons donc des heuristiques, donnant une solution sans garantie d’optimalité. Une manière (bête) pour faire cela de manière non optimale consiste à supprimer tous les sommets du graphe : il n’y a évidement plus aucun cycle dans le graphe. Evidement, cette heuristique ne permet pas de trouver le nombre optimum (minimum) de sommets à supprimer pour résoudre le problème.
Le but de ce projet est de proposer et implémenter un (ou plusieurs) algorithme heuristique non trivial proposant une solution réalisable pour ce problème. C’est à dire qu’il n’est pas demandé d’avoir une solution forcement optimale, mais une solution valide : votre algorithme doit forcement produire un graphe sans cycle une fois tous les sommets supprimés. On souhaite toutefois avoir la solution la plus petite possible (ce qui donnera un classement).
Utilisation du GIT inscription. Une utilisation non standard sera considérée comme suspecte (on attend des commit réguliers de petites tailles) (si vous ne savez pas utiliser GIT, c’est l’occasion d’apprendre)
Un choix et une implémentation d’un graphe comme vu en cours (l’utilisation de librairies externes pour la gestion du graphe est interdite)
La lecture d’un fichier au format imposé par la compétition. Les instances publiques sont disponibles ici. Il y a dans le GIT quelques instances très simples pour que vous puissiez debugger plus simplement (la valeur de la solution optimum est écrite en commentaires dans le fichier). Votre projet doit gérer des instances plus compliquées !
La lecture du graphe doit être faite sur l’entrée standard (stdin) (exemple pour python sur le git), la solution doit être donnée sur la sortie standard (stdout). Cela veut dire qu’il ne doit pas y avoir d’autres messages sur la sortie standard (sinon ils seraient considérés comme dans la solution) ! Utilisez pour le debug soit une macro debug, soit la sortie erreur stderr. La sortie doit être la liste des sommets à supprimer (i.e. la solution). Un script est disponible ici permettant de vérifier que la solution est bien valide (i.e. si la suppression des sommets donnés donne bien un graphe acyclique).
Au moins un algorithme heuristique non trivial produisant une solution valide en moins de 10 minutes dans le langage de votre choix (me contacter en cas de langage exotique), si cela est compatible avec optlio.
Une participation sur optil.io, voir ici sur comment faire pour uploader votre projet sur la plateforme. Merci d’utiliser une référence à dauphine/mido/miage/l3/… dans votre username pour vérification. Pour participer, vous enverez votre code ici (un envoi max par 24h). Pour tester avant, envoyer le code ici (un envoi max par minute) pour vérifier que tout fonctionne.
Votre programme recevra un signal SIGTERM après 10 minutes, vous devez le gérer si votre programme n’a pas terminé après 10 minutes (il y a un exemple en python sur le git). Si vous n’arrivez pas à mettre en place cela, vous pouvez faire en sorte que votre programme s’arête après au plus 10 minutes (avec un timer par exemple).
Une exécution typique de votre programme pourra être:
cat file1.gr | python3 programme.py > solution
ou encore
python3 programme.py < file1.gr > solution
Pour tester le principe du signal, par exemple (envoie un signal SIGTERM après 10 secondes):
Vous avez le droit de regarder dans la littérature pour vous inspirer des bonnes heuristiques, plusieurs articles vous sont proposés ici. Il semble qu’une bonne approche consiste à :
Réduire (preprocessing) le graphe en supprimant des sommets et/ou arcs sans perdre d’information (par exemple, reflechissez à ce que l’on peut faire d’un sommet avec un degré sortant de 0, ou de plusieurs arcs allant d’une composante fortement connexe à une autre)
Trouver une solution initiale de manière itérative (selon différents critères (par ex. les degrés entrants/sortants) éventuellement)
Tenter d’améliorer cette solution à l’aide de la recherche locale (échange de sommets entre solution et non solution, etc)
Vous pouvez relancer plusieurs fois votre algorithme avec des paramètres différents ou des choix randomisés ou faire des tentatives d’amélioration de la solution, afin d’utiliser aux maximum les 10 minutes qui vous sont alloués.
S’il y a différents paramètres pour votre algorithme, essayer d’étudier ce qui marche le mieux selon l’instance à résoudre, avec vos connaissances en Analyse de données.
Rendu
L’utilisation du GIT de github classroom est imposée. S’inscrire ici. Tous vos dépôts seront automatiquement clonés à moment de la deadline et la note se basera sur cet état. Il ne servira donc à rien de continuer à modifier votre code après la deadline.
Le projet est à faire seul.
Utilisez le canal Teams pour toute question relative au projet.
Il est attendu sur le Git :
Les sources du projet dans un répertoire src
Un README à la racine décrivant comment compiler et utiliser votre projet ainsi que votre login sur le site optil.io. Si vous n’utilisez pas python, votre README doit expliquer comment compiler et exécuter votre programme (par exemple avec Ant/Maven et jar pour Java, un Makefile puis la ligne d’éxecution pour du C++ etc).
Un court document doc.pdf indiquant vos approches, vos algorithmes, leurs complexités. Vous ne devez pas copier coller votre code ! Il indiquera également les sources d’articles proposant les algorithmes dont vous vous êtes inspiré ou tout autre code emprunté qui n’est pas de vous. Éventuellement vous donnerez quelques graphes de tests montrant les performances de votre algorithme.
Vous avez le droit de discuter entre vous et de lire des articles, mais vous devez préciser ce qui n’est pas de vous. Un détecteur de plagiat de code sera utilisé.
La note finale prendra en compte votre classement dans le challenge.
