One-sided crossing minimization problem (Projet Algo des graphes L3 MIAGE 2024-2025)
En quelques mots:
Le but de ce projet est de participer à la track heuristic du challenge PACE pour le problème de graphe One-sided crossing minimization (OCM) en proposant un ou plusieurs algorithmes pour le résoudre.
Dates
14 novembre 2024 : mise en ligne du sujet.
Rendu du projet : 4 février 2025, 23h (automatique via Github)
Soutenances : 6 février 2025 (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).
One-sided crossing minimization
Nous considérons dans ce projet des graphes non-orientés bipartis dont les sommets sont répartis en deux couches horizontalesA et B. La couche A est fixée et le but est de trouver la permutation des sommets de la seconde couche B de manière est minimiser le nombre de croisements d’arêtes.
Exemple d’une instance : les sommets de A sont fixés. La première permutation des sommets de B induit 33 croisements d’arêtes, la seconde seulement 17.
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 à ordonner les sommets de la seconde couche (B) de manière aléatoire. Evidement, cette heuristique ne permet pas de trouver le nombre de croisements optimum.
Le but de ce projet est de proposer et 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 plus de la plateforme optil.io (voir plus loin), je lancerai de temps en temps un script testant vos projets dont la sortie se trouvera ici.
Note : l’arête ab croise l’arête uv si a < u et b > v ou si u < a et v > b.
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 l’ordre des sommets de B (i.e. la solution). Un script est disponible ici permettant de vérifier que la solution est bien valide et le nombre de croisements de cette solution (ou un message d’erreur).
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 optl.io.
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.
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 tester tous les ordres ou de compter chaque croisement possible. Ce post de blog répertorie quelques techniques (parfois trop avancées pour vous). Quelques pistes ?
Réduire le grape initialement (comment se comportent les sommets jumeaux ?)
Trouver une première sequence (bête) (les méthodes du barycentre ou de la médiane sont plutôt bonnes) très rapidement sur chaque composante connexe et essayer ensuite de l’améliorer ?
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 LLMs devront être mentionnées. Un détecteur de plagiat de code sera utilisé.
La note finale prendra en compte largement votre score dans le challenge.
Je sais que ce n’est pas un projet facile mais je crois en vous, bon courage!
