MSE3112B : Introduction à la programmation en variables entières (3 ECTS)

Code apogée

MSE3112B

Semestre calendaire

S1

Nombre d'ECTS

3

Intitulé du cours

Optimisation combinatoire - Introduction à la programmation en variables entières

Mots clés

Problèmes combinatoire, complexité, algorithmes combinatoires, et introduction à la programmation entière.

Université

Victor Segalen Bordeaux 2

Composante

UFR Sciences et Modélisation

Département

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 aussi offert en spécialité 4 du même master et aux étudiants du master d'informatique.

Objectifs pédagogique

Donner les outils standard de modélisation (outils de la programmation mathématique et de la théorie des graphes) et de résolution algorithmique de l'optimisation discrète : méthodes exactes et approchées.

Prérequis

licence scientifique

Programme détaillé

• Optimisation dans un espace discret : approche énumerative et explosion combinatoire.
• Complexité des algorithmes (empirique, en moyenne et du pire des cas).
• Problèmes faciles/difficiles : introduction à la théorie de la complexité (classes P, NP, NPC, NP-hard et reduction de problèmes);
• Formulation par la programmation entière : modélisation avec des variables entières, qualité de formulation.
• Optimisation exacte versus approchée : borne primale et duale, relaxation combinatoire, relaxation linéaire, heuristiques constructives.
• Méthode de séparation et évaluation (branch-and-bound).

Summary

Références bibliographiques

1. Berge, Claude. Graphes. 3ème édition. - Gauthier-Villars, 1983.
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

P. Pesneau, A. Raspaud, F. Vanderbeck

Volume horaire

10 heures de cours, 14 heures TD

Modalités de contrôle des connaissances

Ecrit terminal 3h (=2/3 de la note), Contôle continu (Projet, ...) (=1/3 de la note).