Optimisation discrète

Actualités

  • L’information pour l’examen est disponible ici.
  • Le corrigé de l’examen blanc est disponible.
  • Le corrigé 10 et un examen blanc sont disponibles.
  • La série 10 et le corrigé 9 sont disponibles.
  • La série 9 et le corrigé 8 sont disponibles.
  • Pour obtenir le bonus de 0.25, il faut avoir 50% du total des points (y compris l’examen final) du cours en ligne. Autrement dit, vous obtenez le bonus ssi les conditions du certificat Coursera sont remplies.
  • La série 8 est disponible.
 
Voici la fiche de cours.

Description

Pour la première moitié du semestre, on suivra ce cours en ligne. Le jeudi entre 8h et 10h, vous êtes libre de choisir parmi les options suivantes:

  • deux heures de cours en français qui traite le même contenu que le cours en ligne
  • deux heures de consultation et une séance d’exercices prolongée

Pour la deuxième moitié du semestre, on propose de façon alternée deux heures de cours traditionnel (en français) avec la séance d’exercices (une heure) et une heure de cours avec la séance d’exercices de deux heures.

Horaires

Première moitié du semestre (du 18 Février au 11 Avril)

Séances d’exercices :  Jeudi, de 8h à 11h dans les salles

CE 1100 (Franka), CE 1101 (Adrian), CM 012 (Chidambaram), CM 013 (Alfonso), MAA 331 (Carsten)

Cours (optionnel): Jeudi, de 8h15 à 10h, CO 1

 

Deuxième moitié du semestre (du 18 Avril au 30 Mai)

Cours : Jeudi, de 8h15 à 9h / 10h, CO 1

Séances d’exercices :  Jeudi, de 10h / 9h à 11h dans les salles

CE 1100, CE 1101, CM 012, CM 013, MAA 331

 

Horaires de bureau

Adrian :  Mardi 12h – 13h

Alfonso : Jeudi 14h – 15h

Carsten : Vendredi 13h – 14h

Chillu : Vendredi 13h – 14h

Objectifs

Familiariser les étudiants avec des modèles de programmation linéaire et des algorithmes. Leurs apprendre à développer et analyser des algorithmes.

Contenu

Programmation linéaire : 

Algorithme du simplexe
Perturbations et règle lexicographique 
Lemme de Farkas et dualité
Méthode duale du simplexe 
Polyèdres

Couplages et flots dans les réseaux :

Flots maximum 
Couplage biparti et non-biparti
Polytope de couplage.

Matériel du cours

Vous trouvez ici des notes de Cours en anglais et ci-dessous les transparents utilisés dans le Cours.

 

  Contenu Fichiers
Leçon 1 Programmation linéaire: Introduction et exemples 21.02.2013
Leçon 2 La géométrie de la programmation linéaire 28.02.2013
Leçon 3 L’algorithme du simplexe 07.03.2013
Leçon 4 L’algorithme du simplexe est-il efficace ? 14.03.2013
Leçon 5 Dualité, Programmation linéaire en nombres entiers 21.03.2013
Leçon 6 Algorithme de parcours en largeur, Algorithme de Bellman-Ford 28.03.2013
Leçon 7 Algorithme primal-dual 11.04.2013
Leçon 8 Flots dans les réseaux : Introduction  
Leçon 9 Flots et réseaux : l’algorithme de Ford-Fulkerson 25.04.2013
Leçon 10 Flots et réseaux : Théorème flot-max/coupe-min, Edmonds-Karp 02.05.2013
Leçon 11

Flots et réseaux : Edmonds-Karp

Programmation dynamique: problème du sac à dos

16.05.2013
Leçon 12 Programmation dynamique: problème du sac à dos 23.05.2013
Leçon 13 Indications pour l’examen 30.05.2013

 

 

Exercices à rendre

   
Semaine 1 Problem 2 (optional assignments)
Semaine 2 Problem 2 (optional assignments)
Semaine 3 Problem 1 (optional assignments)
Semaine 4 Problem 1 (optional assignments)
Semaine 5 Problem 1 (optional assignments)
Semaine 6 Problem 1 (optional assignments)
Semaine 7 Problem 1 (optional assignments)

 

Exercices

Il y aura des exercices chaque semaine.  Pour la première moitié du semestre, ce seront les exercices obligatoires et optionnels du cours en ligne. Pour la deuxième moitié, il y aura une feuille d’exercices.
 
Il est fortement conseillé de travailler ces exercices seul ou en groupe. La séance d’exercices offre une bonne opportunité d’effectuer la série. Vous pourrez y discuter des exercices et du contenu du cours avec les assistants.
 
Si vous voulez obtenir un bonus pour l’évaluation finale, vous pouvez rendre des solutions écrites aux exercices notés, au plus tard le lundi suivant, avant 12h dans la boîte au bureau MA B1 533. Nous les corrigerons et vous donnerons un retour.
Le rendu peut être fait en groupe de trois personnes au plus.
Chaque jeudi entre 10h et 11h, on discutera les solutions des exercices de la semaine avant.
Pour les exercices à rendre, on choisit un groupe et on lui demande de présenter et expliquer sa solution.
La présentation est faite par une personne du groupe choisi.
 
 

Séries

Solutions

série 08 corrigé 08
série 09 corrigé 09
série 10 corrigé 10
 
 
Examen blanccorrigé (ébauche)

Indications pour les exercices de programmation

Ordinateurs EPFL (dans la salle TP en math, c-à-d MA B1 486) :

1) Ouvrir un terminal

2) Accéder le classeur contenant le fichier avec le code

3) Exécuter python2.6 fichier.py

 

Installation sur Mac ou Linux :

1) installer python 2.7.3 (voir cette page)

2) download sympy-0.7.2.tar.gz (version python 2, voir cette page)

3) Ouvrir un terminal, accéder le classeur contenant sympy et exécuter python setup.py install

 

Windows ou Mac IDLE :

1) installer python 2.7.3 et sympy 0.7.2 (windows executable)

2) Lancer python.

3) Pour ouvrir et exécuter le code dans un fichier :

Ouvrir le fichier (File -> open in a new window)

Dans la nouvelle fenêtre avec le code, choisir Run -> Run module (ou appuyer simplement F5 )

 

En cas de problème, n’hésitez pas à venir voir les assistants pendant les horaires de bureau.

Examen et la note finale

Il y aura un examen écrit à la fin du semestre.

Il est possible d’obtenir un bonus pour la note finale sous conditions:
– un minimum de 50% des points sur les quiz (“assignments”) en ligne (bonus 0.25)
– un minimum de 70% des points sur les rendus et la présentation d’au moins une solution (bonus 0.5)

 

Références

Jiří Matousek and Bernd Gärtner    Understanding and using linear programming. Springer, 2006. ISBN 978-3-540-30697-9 (bibliothèque, en ligne (accessible seulement depuis le reseau de l’EPFL))

Stephen Boyd and Lieven Vandenberghe    Convex Optimization. Cambridge University Press, 2004. ISBN 0521833787 (disponible en ligne)

Jean-François Hêche, Thomas M. Liebling, Dominique de Werra, Recherche opérationnelle pour ingénieurs I (bibliothèque)

Dimitris Bertsimas and John N. Tsitsiklis.     Introduction to linear optimization. Athena Scientific, 1997. ISBN 1-886529-19-1

Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin.     Network flows : theory, algorithms, and applications. Prentice Hall, 1993. ISBN 0-13-617549-X

Thomas Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction à l’algorithmique. MIT Press, 2004. ISBN 978-0262032933 (bibliothèque, site web)