Linköping University

Number of credits: 8 hp

Examiner: Torbjörn Larsson

Aim: The course gives an introduction to the field of linear optimization, including basic modeling, theory and solution methods. It is intended for students in scientific disciplines where linear optimization can serve as tool in research and development, such as management science, logistics management, engineering design, computer science, and electrical engineering. It is also intended as a first course in linear optimization for students in mathematical sciences.

Course literature: Optimization for Decision Making: Linear and Quadratic Models, K.G. Murty, Springer, 2010, and Linear Programming and Network Flows, M.S. Bazaraa, J.J. Jarvis and H.D. Sherali, Wiley, 2013 (4th edition).

Course contents: Linear equations, inequalities, linear programming: a brief historical overview. Formulation techniques involving transformations of variables. Intelligent modeling essential to get good results. Polyhedral geometry. Duality theory and optimality conditions for linear programs. Revised simplex variants of the primal and dual simplex methods and sensitivity analysis. The decomposition principle. Complexity of the simplex algorithm and polynomial-time algorithms. The transportation and assignment problems.

Organisation: Seminars where the participants present the course topics and solutions to selected exercises from the course literature.

Examination: Active participation with presentations of course topics and solutions to exercises.

Prerequisites: Undergraduate courses in mathematics and optimization or operations research.

Presentations from the book by Murty:

Chapters 1 and 2.2
Chapters 2.3-5
Chapter 3
Chapters 4.1-7
Chapters 4.8-13
Chapters 5.1-5
Chapters 5.6-8 and 6.1-4
Chapters 6.7-10
Chapters 6.11-13
Chapters 6.14-7.3
Chapters 7.4-8

Presentations from the book by Bazaraa, Jarvis and Sherali:

Chapters 7.1-3
Chapters 7.4-7
Chapters 8.1-2 and 8.4