Mixed Integer Programming resolution techniques and applications to Sparse Approximation problems

Diego Delle Done (LIX, CNRS - École Polytechnique; L2S)
February 14, 2020 — 11:00 — "Salle des séminaires du L2S, C4.01"

Abstract

Mixed Integer Programs (MIP) represent a powerful tool to model Combinatorial Optimization problems, although the resolution of a MIP is in general an NP-hard problem. Nevertheless, much progress has been made in the last decades to improve the performance of the practical resolution of MIP models, and nowadays, commercial solvers can solve models with thousands of integer variables, in considerable small times.

In this talk we will give an introduction to the basic ideas behind these algorithms, namely, linear programs solving, branch and bound algorithms and cutting planes techniques. We will then illustrate some of these techniques with a MIP formulation for Sparse Approximation problems.

Biography

I got my Computer Scientist degree at the University of Buenos Aires (Faculty of Natural and Exact Sciences), Argentina in 2009 and a PhD in Computer Sciences at the same university in 2016. My main research interests cover topics around combinatorial optimization, applied mathematics, linear integer programming and graph theory. I am also very interested in applied real-life projects concerning these topics.

At present, I have a full-time postdoctoral fellowship position split within the Laboratoire d’Informatique de l’École Polytechnique de Paris (LIX) and the Laboratoire des Signaux et Systèmes (L2S) Centralesupelec, where I’m working on a project which aims to apply several optimization techniques to the resolution of sparse systems in the context of parsimony sampling (or compressive sensing).