Zhentao Li's Homepage

email: firstname.lastname@ens.fr

 // home


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.

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