# Optimization

Optimization

(under construction; rules may change slightly depending on the number of participants)

### 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

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

(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 8: Polyhedra (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.

### 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)