The goal is to learn how to formulate and solve linear optimization models:
- Learn how to formulate linear and integer optimization models;
- Understand how to use the simplex algorithm for linear optimization;
- Understand duality theory and its economic interpretation (shadow prices);
- Learn how to solve integer optimization problems using branch and bound and Gomory cuts.
An important objective is also to learn how to use state-of-the-art optimization software and the modeling language AIMMS, and to use this to solve a realistic case study.
The recommended, but not mandatory, text book will be:
Introduction to Linear Optimization by Dimitris Bertsimas and John N. Tsitsiklis.
Publication: 1997, 608 pages, hardcover
It is therefore recommended, but not formally required, to purchase this book.
Linear optimization is one of the fundamental computational tools in Operations Research, and is used for airline scheduling, production planning, and in many other industrial settings. In fact, it has been called one of the mathematical problems “using up most of the computer time in the world”. We will first look at how linear optimization models arise from practical decision problems. Next we will consider the links with linear algebra and geometry. This will lead us to an algorithm, called the simplex method, that may be implemented using techniques from linear algebra. Every linear optimization problem has an associated dual problem, that has an economic interpretation in terms of “shadow prices”, and we will look at these ideas in some detail. Finally, we will consider the case where the decision variables should take integer values, and study two techniques for such problems, namely branch-and-bound, and Gomory cuts.
Type of instructions
3 hours lecture (English) and 3 hours tutorial/practical (Dutch/English)
Type of exams
Written exam (open questions, weight 0.9) and computer assignments ( weight 0.1). For the resit exam, the written exam has weight 1.0, and there is no computer assigment.