| Crédit : 3 ECTS |
| Langue du cours : anglais
|
|
|
|
Volume horaire
- CM :
15 h
- Volume horaire global (hors stage) :
15 h
Compétences à acquérir
Knowledge about the geometric aspects underlying optimization problems
Description du contenu de l'enseignement
Since its emergence as a fundamental discipline in theoretical computer science, discrete optimization, its methods, and the problems it aims to solve have often been accompanied by geometric considerations. This course focuses on these geometric aspects, particularly polyhedral ones, and their algorithmic and structural implications, from foundational paradigms dating back to the 1950s to more recent ones. The questions raised during the study of these various paradigms will be: Where do these geometric aspects come from? How can they be translated into algorithmic and/or combinatorial properties? Throughout these discoveries, open and current research problems on the various topics covered will be mentioned. Here is a possible list of contents, which might change according to the current trends or the lecturer's inclinations.
- Polyhedra and strong min-max relations
- Extended formulations and communication protocols
- Perfect and box-perfect graphs
- Triangulations of cones and polyhedra
Mode de contrôle des connaissances
It will depend on the number of participants
Bibliographie, lectures recommandées
- M. Conforti, G. Cornuéjols, and G. Zambelli. Integer Programming. Graduate Texts in Mathematics, 271. Springer International Publishing (2014).
- P. Chervet, R. Grappe. A weak box-perfect graph theorem. Journal of Combinatorial Theory, Series B 169: 367-372 (2024).
- P. Chervet, R. Grappe, L.-H. Robert. Box-total dual integrality, box-integrality, and equimodular matrices. Mathematical Programming, 188(1): 319-349 (2021).
Enseignant responsable
ROLAND GRAPPE