Fiches de cours

Discrete optimization

Enseignant(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

Semaine de référence

LuMaMeJeVe
8-9   CE1104
9-10
10-11    CM1221
11-12
12-13
13-14
14-15
15-16
16-17
17-18
18-19
19-20
20-21
21-22

Cours
Exercice, TP
Projet, autre

légende

• Semestre d'automne
• Session d'hiver
• Semestre de printemps
• Session d'été
• Cours en français
• Cours en anglais
• Cours en allemand