Méthodes Continues pour l'Optimisation Combinatoire – COMCOPT

Les problèmes d'optimisation discrets tels que le flot maximum ou le flot de coût minimum représentent le point d’appui de l'informatique-ils constituent des primitives fondamentales pour des algorithmes plus compliqués mis en œuvre dans les systèmes informatiques modernes. Aujourd'hui, la quantité des données collectées et traitées par le logiciel croît à un rythme rapide, qui rend de nombreux algorithmes classiques impossibles à mettre en pratique. Nous proposons de résoudre ce problème en concevant des algorithmes plus rapides pour une série de problèmes fondamentaux impliquant l'optimisation des graphes et des fonctions submodulaires. Nous le faisons en recourant à des techniques basées sur l’optimisation continue, utilisées dans l'apprentissage automatique et le calcul scientifique. Les innovations algorithmiques proposées sont basées sur le développement d'un ensemble de méthodes de points intérieurs qui tirent fortement parti de la structure combinatoire des problèmes.