Seminar


Date : Sept. 26, 2024, 1:30 p.m. - Room :Salle A102

Computational, combinatorial, and geometric Aspects of linear optimization


Antoine DEZA - McMaster University

Finding optimal allocations of resources, scheduling tasks, and designing prototypes are a few of the areas that operations research addresses. In many cases, these problems can be formulated or approximated as linear optimization problems, which involve maximizing or minimizing a linear function over a domain defined by a set of linear inequalities. The simplex and primal-dual interior point methods are currently the most computationally successful algorithms for linear optimization. While the simplex methods follow an edge path, the interior point methods follow the central path. Worst-case constructions have helped provide a deeper understanding of how the combinatorial and geometric structure of the feasible region affect the computational performance of linear optimization algorithms. We will survey recent worst-case constructions for simplex and interior point methods and, in a similar spirit, investigate the following question: How close can two disjoint lattice polytopes contained in a fixed hypercube be? This question arises from various contexts where the minimal distance between such polytopes appears in complexity bounds of optimization algorithms. Based on joint works with Shmuel Onn (Technion), Sebastian Pokutta (ZIB), and Lionel Pournin (Paris XIII)

Biography: Antoine Deza is the Head of Advanced Optimization Laboratory at McMaster University, Ontario, where he has held a Canada Research Chair in Combinatorial Optimization, and has been the Associate Director of MacDATA Institute. 

He is a Fellow of the Fields Institute, Toronto, and a Distinguished Fellow of the Zuse Institute Berlin. He had previously held a faculty position at the Tokyo Institute of Technology where he received his PhD, and longterm visiting positions at Université Paris Saclay, where he has held a Digiteo Chair in Combinatorics and Optimization, and Technion Israel Institute of Technology. His research focuses on the computational, combinatorial, and geometric aspects of linear optimization.

https://experts.mcmaster.ca/display/deza