# Coursebooks

## Discrete optimization

#### Lecturer(s) :

Eisenbrand Friedrich

English

#### Summary

This course is an introduction to linear and discrete optimization. We will discuss linear programming and combinatorial optimization problems like bipartite matchings, shortest paths and flows. Warning: This course is for mathematicians! Strong emphasis is put on formal mathematical proofs.

#### Content

• Linear Programming
• Simplex Algorithm
• Cycling and termination of the simplex algorithm
• Algorithms and Running times
• Diameter of Polyhedra
• Duality Theory
• Graphs and shortest paths
• Max. weight bipartite matchings
• Maximum flows

#### Keywords

Linear Programming

Algorithms

Complexity

Graphs

#### Learning Prerequisites

##### Required courses

Linear Algebra

Discrete Mathematics or Discrete Structures

##### Important concepts to start the course

The student needs to be able to prove theorems

#### Learning Outcomes

By the end of the course, the student must be able to:
• Choose appropriate method for solving basic discrete optimization problem
• Prove basic theorems in linear optimization
• Interpret computational results and relate to theory
• Implement basic algorithms in linear optmization
• Describe methods for solving linear optimization problems
• Create correctness and running time proofs of basic algorithms
• Solve basic linear and discrete optimization problems

#### Transversal skills

• Continue to work through difficulties or initial failure to find optimal solutions.
• Use both general and domain specific IT resources and tools

#### Teaching methods

Ex cathedra lecture, exercises in the classroom and with a computer

#### Expected student activities

Attendance of lectures and exercises

Completion of exercises

Solving supplementary programs with the help of a computer

#### Assessment methods

Written exam during the exam session

#### Resources

##### Bibliography

Dimitris Bertsimas and John N. Tsitsiklis: Introduction to Linear Optimization, Athena Scientific

Alexander Schrijver: Theory of Linear and integer Programming, Wiley

Lecture notes

### Reference week

MoTuWeThFr
8-9   CE1106
9-10
10-11    CM1121
11-12
12-13
13-14
14-15
15-16
16-17
17-18
18-19
19-20
20-21
21-22

Lecture
Exercise, TP
Project, other

### legend

• Autumn semester
• Winter sessions
• Spring semester
• Summer sessions
• Lecture in French
• Lecture in English
• Lecture in German