Recherche efficace de bornes supérieures pour les problèmes d’affectations avec coûts

• Mar 2023 - Present

En 2002, JC Régin a publié un article [1] permettant de déterminer les couples (variable, valeur) qui ne peuvent pas appartenir à solution d’un problème d’affectations avec coûts. L’article a eu un impact assez important, comme en témoigne ses 84 citations, car le problème sous-jacent est très fréquemment rencontré dans les applications réelles. Cependant la méthode proposée reste plutôt théorique car l’algorithme principal appelle systématiquement n fois une recherche de plus courts chemins, afin de déterminer ceux qui sont supérieurs à une valeur donnée. Le développement d’algorithmes efficaces calculant des bornes sur les plus courts chemins entre paires de sommets, comme les algorithmes ALT [2], Precomputed Cluster Distances [3] ou Hub labelling [4], permettent d’envisager le problème sous un autre angle. Nous pouvons ainsi espérer parfois ne plus avoir à effectuer n recherches de plus courts chemins mais beaucoup moins. L’objectif de ce stage est d’appliquer ces nouvelles approches à notre problème et de mesurer leur efficacité en pratique en espérant rendre l’algorithme réellement utilisable pour résoudre des applications réelles. [1] Régin, J-C. Cost-Based Arc Consistency for Global Cardinality Constraints. Constraints An Int. J. 7(3-4): 387-405 (2002) [2] Goldberg, A. V. and Harrelson, C.: Computing the shortest path : A search meets graph theory. In Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, pages 156–165. Society for Industrial and Applied Mathematics, 2005. [3] Maue, J., Sanders, P., and Matijevic, D.: Goal-directed shortest-path queries using precomputed cluster distances. Journal of Experimental Algorithmics (JEA), 14 :3–2, 2010. [4] Cohen, E., Halperin, E., Kaplan, H., and Zwick, U.: Reachability and distance queries via 2-hop labels. SIAM Journal on Computing, 32(5) :1338–1355, 2003.

Tutrice d’informatique

• Oct 2022 - Present

Encadrement de 6 élèves de L3 en cours particulier sur les matières: - Automates et langages - Programmation orientée objet - Programmation fonctionnelle - Algorithmique - Compilation - Paradigmes et interprétations Encadrement de 6 élèves de L3 en cours particulier sur les matières: - Automates et langages - Programmation orientée objet - Programmation fonctionnelle - Algorithmique - Compilation - Paradigmes et interprétations

Calcul d'itinéraires lisses

• Jul 2022 - Aug 2022

L'objectif de ce stage est d'étudier le problème du plus court chemin lisse (SSPP), qui est motivé par le routage sensible au trafic dans les réseaux routiers. L'objectif est de calculer l'itinéraire le plus rapide en fonction de la situation actuelle du trafic tout en évitant les détours indésirables, comme utiliser brièvement une aire de stationnement pour contourner une autoroute encombrée. Il s'agira dans un premier temps de faire une étude bibliographique sur les différentes mesures de lissage qui ont été proposées pour le calcul d'itinéraires, et plus généralement de plus courts chemins. Nous chercherons ensuite à concevoir des algorithmes performants pour le problème du calcul d'itinéraires lisses. Références : Bast, Hannah, et al. "Route planning in transportation networks." Algorithm engineering. Springer, Cham, 2016. 19-80. Zeitz, Tim. "Fast Computation of Shortest Smooth Paths and Uniformly Bounded Stretch with Lazy RPHAST." 20th International Symposium on Experimental Algorithms (SEA 2022). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022. Falek, Amine M., et al. "To re-route, or not to re-route: Impact of real-time re-routing in urban road networks." Journal of Intelligent Transportation Systems 26.2 (2022): 198-212. Delling, Daniel, Dennis Schieferdecker, and Christian Sommer. "Traffic-aware routing in road networks." 2018 IEEE 34th International Conference on Data Engineering (ICDE). IEEE, 2018.

Tutrice d'informatique

• Feb 2022 - Jun 2022

Encadrement de 3 élèves de L1 et L2 en cours particulier sur les matières: - Algorithmique - Programmation impérative Encadrement de 3 élèves de L1 et L2 en cours particulier sur les matières: - Algorithmique - Programmation impérative

Constraint-based cryptarithm solver

• Jul 2021 - Aug 2021

Un cryptarithme () est un casse-tête numérique et logique qui consiste en une équation mathématique où les lettres représentent des chiffres à trouver. L’équation comporte habituellement des opérations mathématiques de base, telles l’addition et la multiplication. L’exemple le plus connu, publié en juillet 1924 dans The Strand Magazine, est dû à Henry Dudeney : ┌──── │ S E N D │ + M O R E │ ---------- │ M O N E Y └──── Ces casse-têtes sont des exemples classiques pour l’apprentissage de la programmation par contraintes, car ils permettent d’illustrer l’expressivité de la modélisation, et les principes essentiels pour la résolution. De plus, les cryptarithmes sont des problèmes difficiles puisque NP-Complets. L’objectif principal de ce stage est de développer une libraire Java basée sur le solveur de contraintes Choco permettant de modéliser et résoudre n’importe quel cryptarithme basé sur une grammaire. Cette libraire sera aussi utilisable avec une interface en ligne de commande. Un objectif secondaire est de développer des interfaces homme-machine pour l’enseignement et la médiation scientifique. La première interface sera une simple page web similaire à [« The Ultimate Alphametics Solver »] (). D’ailleurs, le solveur de cette page est loin d’être ultime puisqu’il est basé sur un algorithme d’énumération assez naïf. La seconde interface sera un bot discord pour espérer une plus large diffusion.

Tutrice d'informatique

• Mar 2021 - Jun 2021

Encadrement de 5 élèves de L3 en cours particulier sur les matières:- Paradigmes et interprétations - Algorithmique

Fablab manager

• Sep 2019 - Jun 2021

Tutrice de mathématiques

• Sep 2020 - Sep 2020

Encadrement de 5 classes de L1 en cours collectif représentant approximativement 100 élèves. Tâches effectuées: - Rappel de cours- Surveillance de QCM - Surveillance d'examen officiel

Employé de magasin

• Jul 2020 - Aug 2020

Accueil du client, mise en rayon et encaissement. Accueil du client, mise en rayon et encaissement.

Employé de magasin

• Jul 2019 - Aug 2019

Accueil du client, mise en rayon et encaissement. Accueil du client, mise en rayon et encaissement.

Employé de magasin

• Jul 2018 - Aug 2018

Accueil du client, mise en rayon et encaissement. Accueil du client, mise en rayon et encaissement.