L'équipe de recherche DOLPHIN a collaboré avec une entreprise sur un système d'échange de dettes entre entreprises. L'idée derrière ce problème peut être illustrée par un exemple simple : si l'entreprise A doit 10 colis de produits à l'entreprise B, et que B doit 10 colis à C, alors on peut simplifier les dettes en considérant que A doit 10 unités à C. D'une manière générale, on cherche à minimiser le coût du remboursement des dettes (en prenant en compte les distances entre les entreprises notamment).
Lorsque le nombre d'entreprises est grand, on a recours à des algorithmes de flot maximum dans des graphes. Ce qui rend le problème intéressant est que certains échanges ne sont pas autorisés. Cela produit un nouveau problème d'optimisation pour lequel aucune méthode n'a pour le moment été proposée.
Le projet a pour but de proposer des méthodes de résolution inspirées des algorithmes classiques pour les problèmes de flot. En fonction des goûts du ou des étudiants, on pourra éventuellement s'intéresser aussi aux propriétés du problème (complexité, etc.).
Objectif : caractériser le problème et implémenter une approche efficace pour résoudre le problème d'épuration de dettes, monter en compétence sur les algorithmes d'optimisation de flots
|
