Optimisation combinatoire et convexe 2015-2016
Ce cours est une introduction aux problèmes et concepts en optimisation combinatoire et convexe. Le but est d'apprendre à reconnaitre, transformer et résoudre ces problèmes d'optimisation.
Nous regarderons de manière plus approfondie les notions de théorie des graphes, de programmation linéaire et de flots vus dans le cours Algorithmique et Programmation.
Une partie du cours traitera de l'analyse convexe, de la dualité et de la théorie des couplages et ses applications. L'autre moitié se porte sur les algorithmes, notamment les algorithmes de premier ordre et les méthodes de point intérieur, du simplexe et de l'ellipsoïde.
Plusieurs applications illustreront les techniques vus dans ce cours.
Description
Étude de problèmes combinatoire, leur formulation en terme de programmes linéaires en nombres entiers et leur résolution par un mélange de techniques combinatoire et programmation linéaire. Algorithmes de résolution de programmes linéaires.
- Couplage général [1, p.137-141] ou ici
- Polytope de couplages d'Edmonds (preuves un peu différentes du cours: [1, p.208-209, p.214-215] ou bien ici et ici])
- L'algorithme du simplexe version géométrique et version algébrique [2, p.129-130] (avec exemple).
- L'algorithme de l'ellipsoide (ou [2, p.163-164] ou ici).
- Oracle de séparation pour couplage parfait maximum
- T-joins et problème du postier [1, p.166-173]
- T-coupes et polytope des T-joins [1, p.177-179] ou ici p.8-13
- Arbre des coupes minimums Gomory-Hu [1, p.78-83]
- Algorithme primal-dual [2, p.151-152] ou ici (mais nous allons d'abord voir un exemple: couplage parfait biparti maximum (ou [1, p.145-147]))
- Approximation primal-dual (problème du sac-à-dos minimum ici p.178-180)
- Matrices unimodulaires [1, p.220-225] (et ici pour une introduction différente au même résultat)
- Decomposition Edmonds-Gallai et formule de Berge-Tutte.
- Autre problème combinatoires
Cours
Enseignants: Alexandre d'Aspremont et Zhentao Li
Horaires: Jeudi, 9h15 - 12h15, salle R.
Evalution
DM1 0.1
DM2 0.1
Projet 0.3
Examen 0.5
Devoir
DM2 pour le 04/12 soir (était le 03/12)
Projet
Vous avez le choix entre les projets suivants:
Dates importantes
- 19/11/2015 Choix de projet
- 07/01/2016 Remise du rapport et code
- 14/01/2016 Soutenances
- 21/01/2016 Examen
Soutenances
Matin du 14/01/2016 en salle R
Présentation de 15-20 minutes suivi de questions. Projecteur disponible, apportez votre ordinateur pour l'utiliser.
Planification finale. À la demande des étudiants, les lettres intermédiaires des noms ont été permutés pour déjouer des robots du web.
- 9:15 Lcua WETSHRDET Semi-definite programming solver
- 9:45 Gllmiuuae ABIUAN Le voyageur de commerce
- 10:15 Hedairn BRRAAL Le voyageur de commerce
- 10:45 Gxegr-esoAel JLYAAON Le voyageur de commerce
- 11:15 Aclilhe AKINN Support Vector Machines
- 11:45 Smay JLASESI Support Vector Machines
- 12:15 Galliumue MEHORTAN Support Vector Machines
Attention: les soutenances ont étés déplacé de 30 min du planing provisoire.
Veuillez nous contacter d'avance en cas de conflit horaire.
Examen
En Salle R, 9h15 - 12h15 (même créneau que le cours).
Vous avez droit à une feuille de notes. Aucun autre matériel permis.
Références
- [1] Combinatorial Optimization, W. J. Cook, W. H. Cunningham, W. R. Pulleyblank and A. Schrijver, Wiley
- [2] Theory of linear and integer programming, A. Schrijver, Wiley
- [3] Combinatorial Optimization MIT Opencourseware
Autre sources de notes en ligne:
|