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 – network flow problems – ellipsoid method and separation

Part 2: Advanced linear optimization methods - the revised simplex method and column generation - Dantzig-Wolfe and Benders' decomposition - integer programming formulations and solution methods- valid inequalities- branch-and-cut

Prerequisites

  • Parts on Linear Programming in any book Introduction to Operations Research.

  • A course on Linear Algebra based on e.g. David C. Lay, Stephen R. Lay and Judi J. McDonald, Linear Algebra and its Applications . For mathematics students their knowledge of Linear Algebra should suffice to match up rather easily.

  • The course is organized by the Dutch Network for the Mathematics of Operations Research and as such meant, among others for Master students in Operations Research.

Lecture notes/Literature

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 (see the section on Lecture Notes/Literature a bit further).

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 (VU/CWI)