Le but de ce projet est de participer à la track heuristic du challenge PACE pour le problème de graphe Directed Feedback Vertex Set* (DFVS) en proposant un ou plusieurs algorithmes pour le résoudre.
Étant 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.
Ce projet consiste à résoudre ce problème, dans le cadre d’un challenge international.
Ce problème est dit difficile à résoudre optimalement avec une complexité polynomiale (NP-difficile). Nous verrons donc des heuristiques, donnant une solution sans garantie d’optimalité mais de bonne qualité en pratique.
Une manière (bête) pour faire cela de manière non optimale consiste à supprimer tous les sommets du graphe : il n’y a évidemment plus aucun cycle dans le graphe. Une autre possibilité, moins radicale, consiste à ajouter des sommets dans une liste tant que leur ajout (dans le sous-graphe induit par cette liste) ne crée pas un cycle et de supprimer tous les autres sommets à la fin.
Évidemment, ces heuristiques ne permettent 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 d’implémenter un (ou plusieurs) algorithme heuristique non trivial (originaux et efficaces) proposant une solution réalisable pour ce problème. C’est-à-dire qu’il n’est pas demandé d’avoir une solution forcément optimale, mais une solution valide : votre algorithme doit forcément produire un graphe sans cycle une fois que tous les sommets déterminés par l’algorithme sont supprimés. On souhaite toutefois avoir la solution la plus petite possible, ce qui donnera un classement.
En effet, votre programme devra résoudre 100 instances différentes de ce problème, avec un temps maximum de 10 minutes par instance. La qualité de la solution pour chacune de ces instances apportera un score entre 0 et 1, et ainsi votre programme aura un score entre 0 et 100 au global. En plus de la plateforme optil.io (voir plus loin), je lancerai de temps en temps un script testant vos projets (automatiquement depuis github) dont la sortie se trouvera ici. La méthode de score sera celle décrite dans la section “scoring” de cette page (en gros, pour chaque instance, aucun point si trop loin de la solution optimum, 1 point si la solution optimum, et améliorer une bonne solution rapporte plus que d’améliorer une solution mauvaise).
Vous êtes encouragés à être créatifs dans vos heuristiques, à comparer plusieurs idées, et même à échouer sur certaines pistes, tant que vous les documentez dans votre rapport.
Une exécution typique de votre programme pourra être (avec les entrées et sorties standards):
cat file1.gr | python3 programme.py > solution
ou encore
python3 programme.py < file1.gr > solution
Pour tester le principe du signal, on peut faire ceci, ce qui envoie un signal SIGTERM après 10 secondes:
timeout 10s python3 programme.py < file1.gr > solution
Vous êtes libres de faire des programmes en plus pour tester différentes propriétés des instances, ou de faire des scripts testant automatiquement votre programme sur l’ensemble des instances (un exemple est donné sur le GIT).
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 (pas besoin de mettre votre nom de famille). Pour participer, vous enverrez votre code ici (un envoi max par 6 heures). Pour tester avant, envoyer le code ici (un envoi max par minute) pour vérifier que tout fonctionne. Attention, ce site ne doit pas être un moyen de tester si votre programme fonctionne, mais indique simplement à peu près le niveau de votre programme. Faites vos tests en local. Le site pourrait être surchargé.
Vous avez le droit de regarder dans la littérature pour vous inspirer des bonnes heuristiques, plusieurs articles vous sont proposés ici.
Attention, certains graphes sont très (très) grands, faites attention à la complexité, faites des approximations.
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 ou gloutonne (selon différents critères (par ex. les degrés entrants/sortants/total?, le nombre de participation à un cycle…) éventuellement), réfléchir aux arcs arrières, etc.
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 au maximum les 10 minutes qui vous sont allouées.
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.
L’utilisation du GIT de github classroom est imposée. S’inscrire ici. Tous vos dépôts seront automatiquement clonés au 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 exclusivement le canal Teams pour toute question relative au projet.
Il est attendu sur votre Git :
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. Les idées ou le code provenant d’autres personnes ou de LLMs devront être mentionnées, dans les commentaires ou dans le rapport. Votre rapport contiendra, si vous êtes concernés, un retour critique et honnête sur votre utilisation d’IAs génératives. Vous pourrez indiquer les différents types de prompts utilisés (par ex. avec des liens vers les historiques de conversations), les retours critiques que vous avez eus sur le code ou algorithmes généré, les avantages et les inconvénients que vous avez identifiés sur l’utilisation de ce type d’outils. Vous devez être capable d’expliquer et justifier tout votre code, avec clarté et précision ! Le but est que vous appreniez des choses autour des graphes et de ses algorithmes.
Un détecteur de plagiat de code entre les soumissions de la classe sera utilisé.
La note finale prendra en compte largement votre score dans le challenge, mais aussi votre inventivité, la correction du programme, les expérimentations et analyses effectuées ainsi que votre capacité à expliquer vos choix et votre code.
Bon courage !