Course Language: English
Lecturer
Assistant
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
- Chapter 1: Linear programming (updated: February 25, 2009)
- Chapter 2: Convex Sets (updated: March 03 2009)
- Chapter 3: The Simplex method (updated: March 17 2009)
- Chapter 4: Termination, cycling and degeneracy (updated: March 30 2009)
- Chapter 5: Strong duality (updated: March 30 2009)
- Chapter 6: The two-phase simplex method (updated: March 31 2009)
- Chapter 7*: The ellipsoid method (DRAFT, updated: May 05 2009)
- Chapter 8*: Polyhedra (DRAFT, updated: June 01 2009)
- Chapter 9: Paths, cycles and flows in graphs (DRAFT, updated: May 22 2009)
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 2: Ensembles 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 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.
- Assignment 1 – ZIMPL file for exercise 2
- Assignment 2 (exercise 4 revised Feb 25, 2009)
- Assignment 3
- Assignment 4
- Assignment 5 (description of lexicographic pivoting rule added (exercise 4), Mar 18, 2009)
- Assignment 6
- Assignment 7 (exercise 2 revised Apr 02, 2009 – Lower bound for variable x5)
- Assignment 8
- Assignment 9
- Assignment 10
- Assignment 11
- Assignment 12
- Solution 1 – ZIMPL file for exercise 2
- Solution 2
- Solution 3
- Solution 4
- Solution 5 (Fixed error in solution of exercise 2; March 31, 2009; Fixed typo in tableau entry in exercise 4; April 06)
- Solution 6 (Added missing nonnegativity constraints for the dual in exercise 3; April 07)
- Solution 7
- Solution 8
- Solution 9
- Solution 10
- Solution 11
- Solution 12
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 Werra, Recherche 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