Prerequisites
Basic knowledge (bachelor level) of linear algebra and graph theory. A first course in Linear Programming (Optimization) will help, especially for non-mathematics students.
Aim of the course
To provide insight in the theory of linear optimization and in the design of advanced practical methods for solving (integer) linear optimization problems.
Part 1: Basic theory and algorithms of linear optimization: - Linear optimization - polyhedra and polytopes - the simplex algorithm - duality - linear inequalities and Farkas' lemma - sensitivity analysis
Part 2: Advanced linear optimization methods - the revised simplex method and column generation - Dantzig-Wolfe and Benders' decomposition - network flow problems - the ellipsoid method - an interior point method - integer programming formulations and solution methods
Examination
The examination consists of a written exam and a re-exam. No homework exercises make part of your grade.
The exam is scheduled Monday 4 June 2018, 13:30-16:30, Edu Beta, Uithof, Utrecht, and the retake is scheduled Monday 25 June 2018, 13:30-16:30, location to be announced. You may check for updates on these data on the website of Mastermath https://elo.mastermath.nl/.
There will not be a third possibility for passing this course in the academic year 2017-2018! Neither any individual oral exam! Thus, students who only attend the retake have only one possibility to pass this academic year and take a deliberate risk, which is fully their own responsibility!
During the examination no books or any other material is allowed
Below you find examples of exams in the past. The first exercise of the exam is always the same: the formulation of the standard Farkas Lemma. As an example of an exam find the exam of May 27, 2013. with answers.
Lecture Notes / Literature
Course materials
The course is covered by the book `Introduction to Linear Optimization', Bertsimas and Tsitsiklis, Athena Scientific 1997, ISBN 1-886529-19-1. According to some students the book cannot be ordered through ball.com or similar companies. It can be ordered directly from the publisher Dynamic Ideas. Since the past has taught that many students do not have the book yet at the start of the course, I make a copy available of the first five chapters.
Next to the book, we make as much as possible lecture notes available that you find in the week descriptions. There, but also in the lecture notes, you also find the Exercises for the week. The notes you see there now are those of last year and may be subject to small changes.
For a more basic course on linear programming I refer to books titled Introduction to Operations Research , e.g. by Hillier and Lieberman, or by Taha. Another very good book on linear programming is written by Chvatal. Everything you ever wish to know about the Theory of Linear and Integer Programming is found in the more advanced book with that title by Lex Schrijver.
Lecturers: L. Stougie M. van den Akker
- Docent: Leen Stougie