Discrete Optimization

Lecturer: Prof. Friedrich Eisenbrand
Assistants: Adrian Bock
  Martin Niemeier
  Laura Sanità
  Rico Zenklusen
Course Language: French
Exercise Language: English

News

  • 29.06.2010: Due to an error in the lecture notes, the proof of Proposition 3.2 will not be required in the exam anymore.
  • 10.06.2010: Exam announcement is online.
  • 04.06.2010: Solutions for sheet 6 are online.
  • 26.05.2010: Slides for tomorrows lecture are online.
  • 20.05.2010: Solutions for exercise sheet 5 and the sample exam are online.
  • 19.05.2010: Exercise sheet 6 is online.
  • 05.05.2010: Slides for lecture 10 are online.
  • 05.05.2010: Minor fix in sheet 5: In exercise 5, we require that the negative cycle is reachable from the source node s.
  • 04.05.2010: Assignment sheet 5 online.
  • 03.05.2010: A sample exam is now available.
  • 28.04.2010: Chapter 06 of lecutre notes online.
  • 24.04.2010: Deadline for exercise sheet 4 extended by one week. Statement (iii) in exercise 4 corrected (as announced in the last exercise session).
  • 19.04.2010: Sample solutions for sheet 3 online.

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
  • Integer programming
  • Total unimodularity
  • Ellipsoid method

Grading and Examination

There will be a written exam at the end of the semester.

Your final grade gets computed with the following formula:

grade = 1/2*ceil(10*p + 2 + b),

where p is the percentage of points obtained in the exam, b is the percentage of bonus points obtained during the semester, and ceil is a function that rounds the argument up to the nearest integer.

The exam is scheduled for July 1th, 12:00 – 15:00 in room SG1. See the announcement

Time and Date

Lecture: Thursdays, 10:15 – 12:00, MA11
Exercise session: Thurdays, 12:15 – 13:00, MA11

Course material

Slides:

Lecture notes:

Sample exam:

A sample exam can be downloaded here. Use this exam for self assessment. Solutions for the sample exam can be found here.

Assignment sheets and exercise sessions

There will be new exercise sheets every two weeks. You are highly encouraged to work on these exercises on your own or in small groups. A good opportunity to work on these exercises will be the exercise sessions in the two weeks after the exercise sheets have been released. There you can discuss the exercises and the contents of the lecture with the assistants.

You can hand in written solutions for marked exercises on the exercise sheets to obtain bonus points. We will correct them and give you feedback. You can hand in your solutions in groups of up to three persons.

Literature

Jiří Matouek 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