Code
IGSF MAT 4202
Level
M1
Graduate
Graduate
Semester
Fall
Domain
Mathématiques
Program
Programme Ingénieur
Language
Anglais/English
ECTS Credits
2,5
Class hours
27
Program Manager(s)
Department
- Réseaux et Services Multimédia Mobiles
Educational team
Organisation
Cours/TD/TP/projet/examen : cours intégré/TP 18/9Learning objectives
After the module MAT 4202, the second year student will be capable of:
- Show fundamental results in optimisation theory.
- Model practical problems through continuous/discrete mathematical programming.
- Propose and apply methods to solve these problems.
- Use optimization solvers.
CDIO Skills
- 1.1.1 - Mathematics (including statistics)
- 1.2 - Core engineering fundamental knowledge and other disciplines
- 1.3 - Advanced engineering fundamental knowledge, methods and tools
- 2.1.1 - Problem Identification and Formulation
- 2.1.2 - Modeling
Keywords
computational complexity, discrete optimization, approximation algorithms, conic optimization
Content
1) : linear programming and column generation
2) : multicommodity flows and network routing
3) : integer programming (polynomial cases)
4) : computational complexity (Turing machines, NP, P, Cook-Levin theorem, reduction examples)
5) : integer programming (branch & bound, gomory cuts)
6) : IP formulations (Clique, Knapsack, Hamiltonian cycle, TSP)
7) : approximation algorithms (travelling salesman problem, vertex cover, knapsack)
8) : semidefinite programming and conic programming
9) : security game
Evaluation
- 1st session : written exam
- 2nd session : oral exam