Exploitation des sous-expressions communes et de la monotonie des fonctions pour les algorithmes de filtrage sur intervalles
Institution:
NiceDisciplines:
Directors:
Abstract EN:
This thesis deals with the solving of nonlinear systems of equations/constraints by interval-based methods. We present four contributions, all of them aiming at improving constraint propagation algorithms. Constraint propagation contracts the variable domains of individual constraints with a revise procedure and propagates the changes to the rest of the system. Our first two contributions are related to monotonicity of functions and to the dependency problem that occurs when a variable appears several times in a function f. In this case, interval-based methods can generally compute only an approximation of the exact range of f. In the same way, these methods cannot contract optimally the variable domains related to an individual constraint. First, we propose a new Mohc-Revise algorithm that computes the optimal contraction of variables (w. R. T. An individual constraint) when the function is monotonic. The second contribution is an Occurrence Grouping technique that transforms a function f into an equivalent function f_opg, such that the range of f_og can be better approximated by using the monotonicity property. The third contribution is related to the common subexpression elimination technique (CES). CSE is a well-known technique mainly used in code optimization. It basically consists in replacing each subexpression g(X) shared by two or more expressions by an auxiliary variable v and adding the new constraint v = g(X). In this thesis, we prove that the use of CSE techniques in interval analysis as a preprocessing can improve the filtering power of constraint propagation algorithms. Finally, we propose a new partial focusing on well-constrained subsystems of size k. Contracting these subsystems can bring additional filtering compared to global contractors (like interval Newton) and revise procedure used in constraint propagation.
Abstract FR:
Cette thèse porte sur les méthodes d’intervalles pour la résolution de systèmes de contraintes non linéaires. Nous présentons quelques contributions, visant toutes à améliorer les algorithmes de propagation de contraintes. Ces algorithmes contractent les domaines des variables d’une contrainte avec une procédure de révision (revise) et propagent les modifications dans le reste du système. Nos deux premières contributions sont liées à la monotonie des fonctions et au problème de dépendance qui se produit quand une variable apparait plusieurs fois dans une fonction f. Dans ce cas, les méthodes d’intervalles ne peuvent généralement calculer qu’une approximation de l’image de f. De même, ces méthodes ne peuvent pas contracter de manière optimale les domaines des variables impliquées dans d’une contrainte. Premièrement, nous proposons un nouvel algorithme Mohc-Revise qui calcule la contraction optimale des variables (par rapport à une contrainte individuelle) quand la fonction est monotone. La seconde contribution de regroupement d’occurrence (Occurrence Grouping) est une technique qui transforme une fonction f en une fonction équivalente f_og, telle que l’image de f_og peut être mieux approximée en utilisant la monotonie de f_og. La troisième contribution est liée à la technique d’élimination de sous-expressions communes (CSE). CSE est une technique bien connue principalement utilisée en optimisation de code. Elle consiste essentiellement à remplacer chaque sous-expression g(X), partagée par deux ou plusieurs expressions, par une variable auxiliaire v et à ajouter la nouvelle contrainte v = g(X). Dans cette thèse, nous prouvons que le prétraitement par des techniques de CSE peut améliorer le filtrage des algorithmes de propagation de contraintes. Enfin, nous proposons une nouvelle consistance partielle basée sur les sous-systèmes bien-contraints de taille k. Contracter ces sous-systèmes peut apporter du filtrage supplémentaire par rapport aux contracteurs globaux (comme Newton intervalles) et par rapport aux procédures de révisions utilisées dans la propagation de contraintes.