Optimization

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 5: Strong Duality

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

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

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 1zimpl file for exercise 4Solutions 1
Handout 2Solutions 2
Handout 3Solutions 3
Handout 4Solutions 4
Handout 5Solutions 5
Handout 6Solutions 6
Handout 7Solutions 7
Handout 8Solutions 8
Handout 9Solutions 9
Handout 10Solutions 10
Handout 11Solutions 11
Handout 12Solutions 12

 

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)