Le but de ce projet est de participer à la track heuristic du challenge PACE pour le problème de graphe Twinwidth en proposant un algorithme pour le résoudre.
Dates
Rendu du projet : 11 février 23h (automatique via Github)
Soutenances : lundi 12 février 16h30+ (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).
7 décembre 2023 : mise en ligne du sujet
18 janvier 2024 : date de fin.
22 janvier : date de la soutenance (salle en attente)
Twinwidth
Dans un graphe non-orienté, plusieurs “mesures” peuvent être définies. Ce projet propose de travailler autour de la “Twinwidth”. Voir cet article de vulgarisation ou celui-ci ou encore wikipedia.
Pour calculer la Twinwidth, on va effectuer une séquence de contractions de paires de sommets jusqu’à arriver à un seul sommet. Durant les contractions, on va se souvenir des “erreurs” effectuer. Pour cela, on va utiliser un tri-graphe, c’est à dire un graphe pouvant avoir des arêtes classiques et des arêtes rouges.
Dans l’exemple, on commence par contracter les sommets e et f. Ceci a pour effet de créer un “nouveau” sommet ef. L’arête avec c reste noire car il y avait une arête entre c et chacun des sommets contracté. Ce n’est pas le cas pour a et d : on se souvient de cette erreur en liant a et d avec ef à l’aide d’une arête rouge. Note : dans le cadre du projet, le sommet ef n’est pas créé : c’est le sommet e qui reste dans le graphe et le sommet f est supprimé (voir ici, l’opération n’est donc pas symétrique). On continue ensuite en contractant a et d et ainsi de suite.
La twinwidth d’un graphe est le degré rouge d’un sommet au cours de la séquence de contractions (dans l’exemple, c’est 2). Le nom twin vient de la notion de jumeaux (twin) dans un graphe : deux sommets sont jumeaux s’ils ont le même voisinage : contracter ces 2 sommets ne crée aucune arête rouge.
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 à contracter aléatoirement des paires de sommets jusqu’à n’avoir plus qu’un seul sommet. Evidement, cette heuristique ne permet pas de trouver la twinwidth optimum.
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 une séquence de contractions valides. On souhaite toutefois avoir la solution la plus petite possible (ce qui donnera un classement). En plus de la plateforme optil.io, je lancerai de temps en temps un script testant vos projets dont la sortie se trouvera ici.
Ce qui est attendu
Obligatoirement
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 dans un autre dossier pour vérification). 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 la liste des paires de sommets à contracter (i.e. la solution). Un script est disponible ici permettant de vérifier que la solution est bien valide.
Au moins un algorithme heuristique non trivial produisant une solution valide en moins de 5 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 (pas besoin de mettre votre nom de famille). Pour participer, vous enverez votre code ici (un envoi max par 2H). Pour tester avant, envoyer le code ici (un envoi max par minute) pour vérifier que tout fonctionne. Attention, sur cette page LITE, un WA sera donné si jamais vous n’avez pas la solution optimale sur cette instance, ce qui n’est PAS demandé pour ce projet. Ne restez pas bloqué sur cela.
Votre programme recevra un signal SIGTERM après 5 minutes, vous devez le gérer si votre programme n’a pas terminé après 5 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 5 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. Attention, certains graphes sont très grands, il va surement être trop couteux de pouvoir choisir la meilleure paire en testant. Quelques pistes ?
Réduire le grape initialement (les degré 0, les degré 1 ?)
Trouver une première sequence (bête) très rapidement sur chaque composante connexe et essayer ensuite de l’améliorer en regardant le sommet créant le plus grand degré rouge ?
Choisir un sommet selon un critère (ou au hasard) et selectionner son meilleur partenaire dans son voisinage ?
Si le temps vient à manquer, finir avec une solution triviale ?
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 5 minutes qui vous sont alloués ?
Rendu
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 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. Ne mettez pas le mot de passe, le login n’est là que pour associer vos scores. 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/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. Les idées ou le code provenant de ChatGPT (ou similaire) devront être mentionnées. Un détecteur de plagiat de code sera utilisé.
La note finale prendra en compte votre classement dans le challenge.
Je sais que ce n’est pas un projet facile mais je crois en vous, bon courage!
