MSE3211B : Flot et Combinatoire - problèmes combinatoires et routage (3 ECTS)

Code apogée

MSE3211B

Semestre calendaire

S2

Nombre d'ECTS

3

Intitulé du cours

Flot et Routage - problèmes combinatoires et routage

Mots clés

Optimisation dans les réseaux, routage et applications à la logistique.

Université

Bordeaux 1

Composante

UFR Mathématiques et Informatique

Département

Ingénierie Mathématique

Mention

Ingénierie Mathématique, Statistique et Economique

Specialité

Ingénierie de la gestion quantitative des opérations et aide à la décision

Mutualisation

ce module est offert aux étudiants du master d'informatique et en option en MATMECA II.

Objectifs pédagogique

Donner les outils standard de modélisation et de résolution algorithmique de l 'optimisation continue.

Prérequis

licence scientifique

Programme détaillé

• Problèmes de flot: network simplex
• Problèmes multi-flot, relaxation Lagrangienne, décomposition par les prix (Dantzig) et par les ressources (Benders)
• Problèmes de flot généralisé, coût convexe.
• Dimensionnement de réseaux.
• Introduction aux problèmes de tournées de véhicules : formulations, variantes, relaxation, approche de décomposition.
• Problèmes de parcours des arcs d'un réseau : formulations, variantes, cas faciles.

Summary

Références bibliographiques

1. Ahuja, R.K., T.L. Magnanti and J.B. Orlin, Prentice Hall, 1993.
2. The Vehicle Routing Problem, P. Toth, D. Vigo, Editors, Siam monographs on Discrete Mathematics and Applications. 2002.

Contact

A. Miller

Equipe pédagogique

A. Miller, P. Pesneau, F. Vanderbeck

Volume horaire

10 heures de cours, 14 heures TD

Modalités de contrôle des connaissances

Ecrit terminal 3h