Vers des théories testables de la programmation linéaire

La programmation linéaire en nombres entiers mixtes (MILP) est un problème
informatique important et est souvent résolus sur des intrants à grande échelle
dans le monde universitaire et industriel. Des progiciels sophistiqués existent
à cette fin, et le paradigme algorithmique utilisé par ces packages est bien
documenté. Ces les algorithmes, qui sont lents et inefficaces selon le
paradigme de l’analyse du pire des cas, sont néanmoins très efficace en
pratique. Ce décalage entre théorie et observation vaut pour presque tous les
composants algorithmiques utilisés dans le logiciel MILP et constitue un défi
pour l'étude de complexité algorithmique. L'objectif de ce projet est de
développer de nouveaux outils mathématiques pour comprendre les performances de
ces algorithmes.

Le sujet spécifique de ce projet sera la méthode simplexe pour la Programmation
Linéaire (LP), une algorithme de pointe qui est essentiel dans tout solveur
MILP réussi. Un certain nombre de théories des modèles ont déjà été proposés
pour expliquer pourquoi la méthode simplexe est efficace en pratique, y compris
l'analyse de cas moyen, l'analyse lissée et les analyses paramétrées.  Malgré
cet effort concerté, les approches existantes présentent un certain nombre de
limites majeures.

L’objectif du projet est de développer de nouvelles approches mathématiques qui
répondent à ces limites.  Le résultat souhaité de cette ligne de travail est un
cadre mathématique pour expliquer la performance de la méthode simplexe, et
dont les affirmations peuvent être testées dans des expériences informatiques
sur le monde réel données. Le principal résultat du projet concernera les
théorèmes sur la géométrie et la combinatoire du LP.  problèmes et polyèdres
convexes. Le cas échéant, des expériences informatiques seront réalisées.