Aspects géométriques de l'optimisation discrète

Objectifs:
Depuis son émergence en tant que discipline fondamentale de l'informatique théorique, l'optimisation discrète, ses méthodes et les problèmes qu'elle cherche à résoudre ont souvent été accompagnés de considérations géométriques. Ce cours se penche sur ces aspects géométriques, en particuliers polyédraux, et sur leurs impacts algorithmiques et structurels, depuis les paradigmes fondateurs remontant aux années 1950 jusqu’aux plus récents, notamment ceux liés à l’émergence des réseaux de neurones. Les questions abordées lors de l'étude de ces différents paradigmes seront les suivantes : d'où proviennent ces aspects géométriques et comment les traduire en propriétés algorithmiques et/ou combinatoires ?
Tout au long du cours, des problèmes de recherche ouverts et d'actualité seront mentionnés dans les différents thèmes abordés.

Contenu:
Polyèdres et relations min-max fortes
Formulations étendues et protocoles de communication
Polyèdres dans les réseaux de neurones ReLU
Géométrie tropicale et réseaux de neurones profonds

Bibliographie:
M. Conforti, G. Cornuéjols, and G. Zambelli. Integer Programming. Graduate Texts in Mathematics, 271. Springer International Publishing (2014).
P. Chervet, R. Grappe, L.-H. Robert. Box-Total Dual Integrality, Box-Integrality, and Equimodular Matrices. Mathematical Programming, 188 (2021).
J. Huchette, G. Muñoz, T. Serra, C. Tsay. When Deep Learning Meets Polyhedral Theory: A Survey (2023).