Le but de ce projet est de participer à la track heuristic du challenge PACE 2025 pour le problème de graphe Dominating Set (DS) en proposant un ou plusieurs algorithmes pour le résoudre.
Nous considérons dans ce projet des graphes non-orientés non pondérés. Le but est de trouver un sous-ensemble D de sommets de la plus petite taille possible tel que chaque sommet du graphe est soit dans D, soit un voisin d’un sommet de D.
Ce problème sert dans de nombreuses applications pratiques (réseaux sans-fil etc).
Dans l’exemple ci-dessus (tiré de Wikipedia), on voit 3 dominating set possibles (en rouge) pour un même graphe. Celui en (a) est de taille 3, ceux en (b) et (c) sont de taille 2. Il n’en existe pas de taille 1.
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-complet). Nous verrons donc des heuristiques, donnant une solution sans garantie d’optimalité mais de bonne qualité en pratique.
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 forcement optimale, mais une solution valide. 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 5 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 > solutionou encore
python3 programme.py < file1.gr > solutionPour 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 > solutionVous ê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 enverez votre code ici (un envoi max par 5H). 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. Quelques pistes :
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 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 et le nombre 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. Tout code non marqué comme ne venant pas de vous pourra être soumis à des questions techniques précises.
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é.
Bon courage !