Algorithme dynamique de simplexe pour réseaux

Encadrants :S. Balev et A. Dutot

Résumé :L'algorithme de simplexe pour réseaux est une adaptation de l'algorithme classique de simplexe permettant de résoudre efficacement plusieurs classes de problèmes d'optimisation sur graphes. Nous avons implementé cet algorithme en Java et nous envisageons de l'intégrerdans GraphStream.

La première phase de ce projet consiste à étudier et à comprendre le fonctionnement de cet algorithme, de prendre en main et de tester notre implémentation. Pour l'instant celle-ci ne prend pas en compte les changements dans le graphe. La deuxième phase du projet consistera à rendre l'algorithme dynamique en ré-optimisant la solution courante après chaque changement dans le graphe.

Références :[1] D. Kelly, G. O'Neil. The minimum cost flow problem and the networksimplex method, http://www.derekroconnor.net/home/PAPERS/MMS-91.pdf[2] GraphStream, a dynamic graph library, http://graphstream-project.org/