Ce mémoire traite essentiellement de la résolution de systèmes de contraintes (équations et/ou inégalités) non linéaires (plus précisément, non convexes) sur les réels par des méthodes à intervalles. Ces méthodes font principalement appel à des algorithmes de réduction de l'espace de recherche issus de trois communautés aux cultures relativement éloignées : l'analyse numérique (mathématiques), la programmation mathématique (recherche opérationnelle) et la programmation par contraintes (informatique).
Je détaille différentes contributions en programmation par
contraintes sur intervalles (PPCI). Parmi elles, trois algorithmes
nouveaux forment une stratégie de réduction de l'espace de recherche
très compétitive. Un prétraitement est d'abord effectué par un
algorithme qui exploite les sous-expressions communes dans les
contraintes et permet d'obtenir du filtrage additionnel par la
suite. Pendant la recherche arborescente qui suit, un deuxième
algorithme de rognage effectue des "points de choix en temps
polynomial" pour éliminer des tranches aux bornes des intervalles. Il
réhabilite l'algorithme existant de 3B-consistance en l'étendant avec,
entre autres, de la disjonction constructive issue de la
programmation par contraintes sur domaines discrets. Le troisième
algorithme est la procédure utilisée par l'algorithme de rognage pour
éliminer une tranche donnée. Il s'agit d'un algorithme de propagation
de contraintes qui exploite la monotonie des fonctions et qui se pose
comme alternative aux algorithmes de référence Box
et HC4.
Je souligne deux raisons expliquant l'essor des méthodes à intervalles dans des domaines applicatifs variés comme la robotique, l'automatique ou la chimie : d'abord, le fait que les méthodes à intervalles sont parfois seules capables de traiter certains systèmes de contraintes (par exemple ceux dont les coefficients des contraintes sont connus avec une erreur bornée) ; ensuite, le fait que les algorithmes de PPCI entraînent déjà et vont entraîner encore prochainement des gains de performance importants. Ces progrès offrent l'espoir de compléter ou d'être compétitif avec les méthodes de relaxation linéaire ou convexe qui sont utilisées en optimisation globale sous contraintes.
J'introduis également mes trois autres domaines de recherche depuis la thèse : les contraintes fonctionnelles, la décomposition et résolution de systèmes de contraintes (géométriques), la recherche locale pour l'optimisation combinatoire.