MSE3314 : Programmation entière (6 ECTS)

rm

Code apogée

MSE3314

Semestre calendaire

S1

Nombre d'ECTS

6

Intitulé du cours

Programmation entière

Mots clés

Approches polyédrale et Lagrangienne, techniques de reformulation et de décomposition, programmation dynamique avancée, heuristiques primales, et applications

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

Maîtrise de la modélisation par la programmation en nombres entiers, des algorithmes exactes et approchés et de l'utilisation des logiciels de programmation entière.

Prérequis

Programme détaillé

• Problèmes entiers faciles : Matrice TU, algorithmes combinatoires.
• Caractérisation géométrique des polyèdres, qualité de formulation, préprocessing, inégalités valides, faces, et facettes.
• Approche polyédrale : famille générique d'inégalités, algorithme des plans coupants, Branch-and-Cut.
• Programmation dynamique déterministe.
• Relaxation Lagrangienne et dualité.
• Décomposition de Dantzig-Wolfe et décomposition de Benders
• Procédure de génération de colonnes, Branch-and-Price-and-Cut.
• Heuristiques primales.
• Introduction à la programmation par contraintes.
• Théorie de la complexité : optimisation et séparation, approximabilité.

Summary

Références bibliographiques

1. Ahuja, R.K., T.L. Magnanti and J.B. Orlin, Network Flows : Theory, Algorithms and Applications, Prentice Hall, 1993.
2. Cook, W.J., W.H. Cunningham, W.R. PulleyBlank and A. Schrijver, Combinatorial Optimization, Willey, 1998.
3. Papadimitriou, Combinatorial Optimization.
4. Wolsey, L. A., Integer Programming, John Wiley, 1998 (ISBN 0-471-28366-5).

Contact

F. Vanderbeck

Equipe pédagogique

F. Vanderbeck

Volume horaire

cours 40 hetd

Modalités de contrôle des connaissances

Ecrit terminal (=2/3 de la note) + projet (=1/3 de la note)