1) Prerequisites
Basic knowledge of linear algebra and linear programming. The necessary background on linear algebra should be covered by an book textbook, e.g., "Linear algebra and its applications" by David C. Lay, Stephen R. Lay, and Judi H. McDonald. Background information on linear programming can be found in the book "Introduction to linear optimization" by D. Bertsimas and John N. Tsitsiklis.
2) Aim of the course
The field of mathematical optimization concerns the problem of finding the maximum or minimum value of a function over some variable domain. Optimization has many applications, e.g., in risk minimization of portfolios, the optimal design of wings of airplanes, or finding efficient train schedules. Despite its broad range of applications, many disciplines within the field of optimization have a common core element: linear programming. A good understanding of linear programming is thus important to develop mathematical theory and practically effective algorithms for solving optimization problems. In this course, we will therefore provide insights in the theory of linear optimization and in the design of advanced practical methods for solving (integer) linear optimization problems. The course is split into two parts, where the first part covers more theoretical aspects of linear programming and the second part concerns practical algorithms 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
3) Lecturers
Stan van Hoesel
Christopher Hojny
4) Rules about Homework/Exam We are offering weekly homework exercises to practice the content of the lectures. The homework, however, is not graded and thus does not contribute to the final grade. The final grade is completely determined by a written exam. There will be a regular exam and a resit. Both the regular exam and resit are closed book exams, that is, you are not allowed to bring any accompanying material to the exam.
4) Lecture notes/Literature Most parts of the course are 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 bol.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, we make a copy available of the first five chapters (see the section on Lecture Notes/Literature a bit further). In the second part of the course, we refer for the part on branch-and-cut to "Integer and Combinatorial Optimization", Nemhauser and Wolsey, John Wiley & Sons, ISBN 0-471-35943-2, which should be available as a free e-print via university libraries. Next to the book, we make as much as possible lecture notes and/or slides available that you find in the weekly descriptions. There, but also in the lecture notes or on separate exercise sheets, 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 we refer to books "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. Courses with topics related to Advanced Linear Programming are, e.g.,:
- Continuous Optimization [link: https://elo.mastermath.nl/enrol/index.php?id=1025]
- Discrete Optimization [link: https://elo.mastermath.nl/enrol/index.php?id=1023]
- Scheduling [link: https://elo.mastermath.nl/enrol/index.php?id=553]
- Algorithms Beyond the Worst Case [link: https://elo.mastermath.nl/enrol/index.php?id=481]
- Docent: Christopher Hojny
- Docent: Stan van Hoesel