Geometric Aspects of Discrete Optimization

Objectives:
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, especially those related to the emergence of neural networks. 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 the course, open and current research problems on the various topics covered will be mentioned.

Content:
Polyhedra and strong min-max relations
Extended formulations and communication protocols
Polyhedra in ReLU neural networks
Tropical geometry and deep neural networks

Bibliography:
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).