Linear Programming, 6.0 credits

Entry requirements

Undergraduate courses in mathematics and optimization or operations research.

Contents

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.

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.

Educational methods

The course consists of nine seminars which (except the first one) will be arranged in subgroups of three or four students. Before each seminar

• every student has studied the corresponding chapters in the course book.
• two students have prepared one presentation each according to the instructions.
• For two seminars, an algorithm implementation is also needed.
• every student has solved the assigned exercises, and one additional exercise arbitrarily chosen from the chapter.
• The solutions to the exercises should be distributed to all subgroup members and to the examiner at least two working days in advance of the seminar.

Examination

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

Grading

Course literature

"Introduction to Linear Optimization" by D. Bertsimas and J.N. Tsisiklis (1997), Athena Scientific, Belmont, Massachusetts.