Discrete optimization
Summary
This course is an introduction to linear and discrete optimization. Warning: This is a mathematics course! While much of the course will be algorithmic in nature, you will still need to be able to prove theorems.
Content
- Optimization techniques
- Algorithms and complexity
- Linear Programming
- Simplex Algorithm
- Duality Theory
- Integer Programming and relaxations
- Network flows
Keywords
Linear Programming, Algorithms, Complexity, Graphs, Optimization
Learning Prerequisites
Required courses
Linear Algebra
Recommended courses
Discrete Mathematics or Discrete Structures
Important concepts to start the course
The student needs to be comfortable reading and writing formal mathematical proofs.
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
Dans le cas de l'art. 3 al. 5 du Règlement de section, l'enseignant décide de la forme de l'examen qu'il communique aux étudiants concernés.
Resources
Bibliography
Dimitris Bertsimas and John N. Tsitsiklis: Introduction to Linear Optimization, Athena Scientific
Ressources en bibliothèque
Notes/Handbook
Lecture notes
Moodle Link
Dans les plans d'études
- Semestre: Printemps
- Forme de l'examen: Ecrit (session d'été)
- Matière examinée: Discrete optimization
- Cours: 2 Heure(s) hebdo x 14 semaines
- Exercices: 2 Heure(s) hebdo x 14 semaines
- Type: optionnel
- Semestre: Printemps
- Forme de l'examen: Ecrit (session d'été)
- Matière examinée: Discrete optimization
- Cours: 2 Heure(s) hebdo x 14 semaines
- Exercices: 2 Heure(s) hebdo x 14 semaines
- Type: optionnel
- Semestre: Printemps
- Forme de l'examen: Ecrit (session d'été)
- Matière examinée: Discrete optimization
- Cours: 2 Heure(s) hebdo x 14 semaines
- Exercices: 2 Heure(s) hebdo x 14 semaines
- Type: optionnel
- Semestre: Printemps
- Forme de l'examen: Ecrit (session d'été)
- Matière examinée: Discrete optimization
- Cours: 2 Heure(s) hebdo x 14 semaines
- Exercices: 2 Heure(s) hebdo x 14 semaines
- Type: optionnel
- Semestre: Printemps
- Forme de l'examen: Ecrit (session d'été)
- Matière examinée: Discrete optimization
- Cours: 2 Heure(s) hebdo x 14 semaines
- Exercices: 2 Heure(s) hebdo x 14 semaines
- Type: optionnel
- Semestre: Printemps
- Forme de l'examen: Ecrit (session d'été)
- Matière examinée: Discrete optimization
- Cours: 2 Heure(s) hebdo x 14 semaines
- Exercices: 2 Heure(s) hebdo x 14 semaines
- Type: optionnel
Semaine de référence
Lu | Ma | Me | Je | Ve | |
8-9 | |||||
9-10 | |||||
10-11 | |||||
11-12 | |||||
12-13 | |||||
13-14 | |||||
14-15 | |||||
15-16 | |||||
16-17 | |||||
17-18 | |||||
18-19 | |||||
19-20 | |||||
20-21 | |||||
21-22 |
Légendes:
Cours
Exercice, TP
Projet, labo, autre