Optimisation combinatoire et convexe
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 notes [1, p.137-141] ou ici
- Polytope de couplages d'Edmonds notes. Une 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] scan de ces pages (avec exemple).
- L'algorithme de l'ellipsoide (ou [2, p.163-164] ou ici).
- Oracle de séparation pour couplage parfait maximum notes
- T-joins et problème du postier notes [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 notes ou ici ou [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]))
Cours
Enseignants: Alexandre d'Aspremont et Zhentao Li
Horaires: Jeudi, 9h15 - 12h15, salle R.
Plan
Planification provisoire:
- 03/11: Introduction. Rappel sur le couplage. Polytope des couplages d'Edmonds.
- 10/11: Fin polytope des couplages.
- 17/11: Pas de cours
- 24/11: Simplex géométrique et algébrique. Conséquences de l'algorithme de l'Ellipsoïde. Oracle de séparation.
- 1/12: Fin oracle de séparation. T-joins et problème du postier.
- 8/12: T-coupes et polytope des T-joins.
- 1/5: Fin T-coupes et polytope des T-joins. Algorithmes primal-dual.
TD
Evalution
DM1 0.1
DM2 0.1
Projet 0.3
Examen 0.5
Devoir
DM2 pour le 9/12. Veuillez m'envoyer vos solutions tapés par mail. (Vous pouvez inclure des scans de figures (uniquement de figures).)
06/12 Exercice 2, question 2 et 3 ont été mis à jours.
Projet
Vous devez compléter un projet parmis les suivants, en binôme.
SVP, nous envoyer le nom de binôme et projet chosis à zhentao li ens fr et aspremon ens fr (avec les ponctuations ajoutés à ces adresses), au plus tard le 17/11.
Dates importantes
- 17/11/2016 Choix de projet
- 04/01/2017 Remise du rapport et code par mail avant 16h
- 12/01/2017 Soutenances
- 19/01/2017 Examen
Soutenances
Matin du 12/01/2017 en salle R
Présentation de 15-20 minutes suivi de questions. Projecteur disponible, apportez votre ordinateur pour l'utiliser.
Planification provisoire. Les lettres intermédiair
es des noms ont été permutés pour déjouer des robots du web.
- 9:15 Jseoph de Vraimeslt, Juels Pnoadrd, SVM
- 9:40 Koaiwsrn Kuatme, Cmléncee Rdéa, SVM
- 10:05 Rméi Jéqzeéul, Mihai Dumansu, SDP
- 10:30 Noliacs Nploan, Cméelnt Basruser, voyageur de commerce
- 10:55 Ncilaos Aoussad, voyageur de commerce
- 11:20 Ntnëahaal Coanrut, David Salipuc, voyageur de commerce
- 11:45 Alaimue Loepz, Gataën Duenoeau, voyageur de commerce
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:
Ancienne page
|