Stabilité numérique des algorithmes d’optimisation

Contexte :
L’utilisation de l’arithmétique flottante par les unités de calcul des ordinateurs pose en pratique de
nombreuses questions, dans la mesure où les algorithmes implémentés ne se comportent pas de la même
façon que leur version idéalisée en arithmétique réelle.
Les programmes linéaires en nombres entiers (PLNE), qui sont utilisés pour modéliser de nombreux
problèmes de recherche opérationnelle, ne font pas exception à la règle. En effet, les pertes de précision
numérique accumulées au cours de la résolution peuvent affecter de manière significative l’exécution des
schémas de Branch & Cut (B&C) sur lesquels s’appuient les solveurs de PLNE. Cette situation est due au
fait que les performances des schémas B&C ne sont pas garanties en termes de temps de calcul et
dépendent fortement, pour une instance de problème donnée, d’un grand nombre de décisions de
branchement. Ces branchements sont eux-mêmes potentiellement numériquement instables, dans la
mesure où ils s'appuient sur des évaluations numériques qui peuvent être proches pour différents
candidats.
Descriptif :
Des travaux précédents ont été menés sur un problème de planification de production d'unités
hydrauliques. Au-delà de la variabilité des performances, il a été montré que des erreurs numériques en
calcul flottant ont une incidence importante sur la faisabilité du problème et sur la qualité de la solution.
Nous nous proposons dans ce stage de poursuivre l’analyse fine de la stabilité du processus de résolution,
en utilisant des techniques d’arithmétique stochastique qui permettent d’évaluer l’impact des pertes de
précision dues à l’arithmétique flottante.
L'objectif de ce stage est de développer un cadre permettant de mettre en œuvre une arithmétique
stochastique au cœur du schéma de B&C. On s’appuira pour cela d’une part sur un solveur à sources
accessibles (comme par exemple SCIP) ; d’autre part sur des outils d’instrumentation en arithmétique
stochastique (comme CADNA ou Verrou). On attend en fin de stage une plateforme de référence pour
l'analyse de l'impact des erreurs numériques pour la résolution de PLNE, ainsi que des éléments permettant
d'identifier précisément quelles parties du schéma de B&C sont plus sensibles aux erreurs. Suite à cette
analyse, un