Introduction to Discrete Optimization

Course Language:  English

Assistant

Martin Niemeier

News

  • 15.05.2009: The midterm exam is now available for download
  • 12.05.2009: The date for the final exam is Monday, 15.06.2009 at 09:00 in rooms INM200 and INM 202.
  • 11.05.2009: The optimization contest is now live. Details can be found here
  • 03.04.2009: There will be no exercise session on April 07 (due to the midterm exam).
  • 23.03.2009: The date for the midterm exam is April 07 (during the lecture).
  • 18.03.2009: The mode of the exercise sessions has changed. Starting next week, you can use the exercise sessions to work in groups on the current assignment sheet and to discuss questions about the lecture and the exercises with the assistant.
  • 20.02.2009: The mailing list “ido-spring-2009 groupes.epfl.ch” has been created.
    To subscribe you have to join the group ido-spring-2009  here.
    Its purpose is to broadcast announcements for the lecture. 
    Students are encouraged to use it for discussion of lecture related topics aswell.

Objectives

Acquaint students with (integer) linear programming models and algorithms. To train them to design and analyze algorithms for discrete optimization problems and network flows.

Topics

Linear programming :

Simplex algorithm
Perturbation and lexicographic rule
Farkas lemma and duality
Dual simplex method

Network Flows and Matchings :

Max st-flows
Bipartite matching
Minimum cost network flows
Parametric search
 

Grading

The grade is determined by the midterm exam (30%) and the final exam (70%).

There is a bonus system which rewards the successful solution of the problem sets. Turned in solutions are corrected and are either fail or pass. The bonus is added to the final grade and is calculated with the following formula

min{1,(10/8)(a/n)},

where a is the number of passes and n is the total  number of sheets published starting with the third sheet. 

Schedule

Lectures Tuesday 16:15-18:00, CM3
Exercise sessions: Tuesday 18:15-19:00, CM3 (First exercise session starts February, 24)
Midterm exam: 07.04.2009 (during the lecture), see the announcement.
Final exam: Monday, 15.06.2009,  09:00 am, in rooms INM200 and INM202, see the announcement.

 

 

Lecture notes

Note: The chapters marked with * are not relevant for the exam.

Lecture notes in french

Here are French translations of the lecture notes, translated by Mme Grünenfelder. Please contact her if you find any mistakes.

Chapitre 1: Programmation linéaire et linéaire entière (updated April 3, 2009)

Chapitre 2Ensembles convexes et polyèdres (updated April 3, 2009)

Chapitre 3: Le développement de la méthode du simplexe (updated April 3, 2009)

Chapitre 4: Terminaison, cyclage et dégénérescence

Chapitre 5: Dualité forte

Chapitre 6: La méthode du simplexe à deux phases

Assignments

There is one assignment sheet every week, which will be published every monday evening on this website. 

In the exercise session you can work in groups on the current assignment sheet and discuss questions about the lecture and the exercises with the assistant.

Solutions to the assignment sheets will be published on this website aswell.

You have the opportunity to hand in your written solutions till the next Tuesday, 18:00, in room MA B1 533 or in the lecture room before the exercise session starts. They will be corrected and returned at the beginning of the next exercise session.
  

Textbooks

Jiří Matoušek and Bernd Gärtner    Understanding and using linear programming. Springer, 2006. ISBN 978-3-540-30697-9 (library, online (from the EPFL network only))

Stephen Boyd and Lieven Vandenberghe    Convex Optimization. Cambridge University Press, 2004. ISBN 0521833787 (available online)

Jean-François Hêche, Thomas M. Liebling, Dominique de WerraRecherche opérationnelle pour ingénieurs I (library)

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