Optimization
(under construction; rules may change slightly depending on the number of participants)
Lecturer
Assistants
Objectives
Acquaint students with linear programming models and algorithms. To train them to design and analyze algorithms.
Topics
Linear Programming:
Simplex algorithm
Perturbation and lexicographic rule
Farkas lemma and duality
Dual simplex method
Polyhedra
Network Flows and Matchings:
Max st-flows
Bipartite and non-bipartite Matchings
Matching polytope
Grading
The final grade consists of 30% from a midterm exam and of 70% of a final written exam of 120 min.
Schedule
Lecture: Thursday 9:15 – 11:00 (MA 11)
Exercise session: Thursday 11:15 – 12:00 (MA 11)
Midterm exam: April 9 (during lecture), see also the announcement; the midterm
Final exam: June 17, 14:15, room CM1, see the announcement
Lecture notes
Chapter 1: Linear programming (updated: February 25, 2009)
Chapter 2: Convex sets (updated: February 25, 2009)
Chapter 3: The development of the simplex method (updated: March 18, 2009)
Chapter 4: Termination, Cycling, and Degeneracy (updated: March 25, 2009)
Chapter 6: The two-phase simplex method
Chapter 7: The ellipsoid method (DRAFT)
Chapter 8: Polyhedra (DRAFT)
Chapter 9: Paths, cycles, and flows (DRAFT)
Lecture notes in French
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
Changed rules:
There is an assignment sheet each week, which is published Wednesday evening on this website. During the exercise session on Thursday, you will have time to work on the exercises and ask questions. Note that, generally speaking, you will have to work on the exercises outside the exercise session to be successful.
You may hand in your written solutions to the exercises the following Thursday (that is, 8 days after the assignment sheet is published) and we will correct them to give you feedback on your solutions.
Handout 1 – zimpl file for exercise 4 – Solutions 1
Handout 2 – Solutions 2
Handout 3 – Solutions 3
Handout 4 – Solutions 4
Handout 5 – Solutions 5
Handout 6 – Solutions 6
Handout 7 – Solutions 7
Handout 8 – Solutions 8
Handout 9 – Solutions 9
Handout 10 – Solutions 10
Handout 11 – Solutions 11
Handout 12 – Solutions 12
Links
Literature
Jiří Matoušek, Bernd Gärtner, Understanding and using linear programming (library, online (from the EPFL network only))
Dimitris Bertsimas, John N. Tsitsiklis, Introduction to linear optimization (library)
Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin, Network flows : theory, algorithms, and applications (library)
Stephen Boyd, Lieven Vandenberghe, Convex Optimization (library, online)
Jean-François Hêche, Thomas M. Liebling, Dominique de Werra, Recherche opérationnelle pour ingénieurs I (library)