Filtering algorithms for stochastic and multi-objective constraints

De nombreux problèmes réels peuvent être représentés comme des problèmes combinatoires, des problèmes pour lesquels trouver une solution revient à trouver une combinaison de valeurs tout en respectant des contraintes définies. Parmi ces problèmes, on peut retrouver par exemple le problème du voyageur de commerce ou bien des problèmes d'ordonnancement. Il y a deux manières de résoudre ces problèmes : soit une méthode spécifique au problème a été développée, auquel cas cette méthode est utilisée, soit un « solveur » général est utilisé. Parmi les solveurs généraux, on retrouve les solveurs utilisant la Programmation par Contraintes (PPC). Les solveurs PPC impliquent différents mécanismes afin de résoudre les problèmes efficacement. Parmi ces mécanismes, on retrouve le filtrage qui permet de supprimer des possibilités qui ne satisfont pas certaines contraintes du problème. Cela peut permettre de réduire exponentiellement l'espace de recherche. Les algorithmes de filtrage sont énormément utilisés lors d'une résolution de problème, optimiser leurs performances est donc essentiel. Dans cette thèse, nous proposons de nouveaux algorithmes pour les filtrages des contraintes généralement utilisées dans les problèmes stochastiques ou ayant plusieurs objectifs à optimiser. Les méthodes proposées se basent principalement sur l'utilisation des Diagrammes de Décision Multivalués (MDD). Un MDD est une structure de données qui permet de représenter de manière compressée un ensemble de tuples. La compression offerte par les MDD peut être élevée, ce qui peut entraîner un gain de performances sur les méthodes de filtrage utilisant ces ensembles, comme les contraintes de table par exemple. La première partie de cette thèse se concentre sur l'utilisation des MDD pour représenter les tuples d'une contrainte de produit. Dans les problèmes incluant des événements aléatoires, la contrainte de produit peut être utilisée pour garantir la robustesse des solutions trouvées en contraignant ces solutions à avoir une haute probabilité d'être réalisables. Nous montrons que la construction d'un MDD représentant les solutions d'une telle contrainte est complexe, principalement à cause des problèmes de débordement d'entier, pouvant se produire suite à des multiplications répétées de variables. Nous proposons donc différentes méthodes afin de surmonter ces problèmes tout en garantissant des propriétés importantes sur le MDD obtenu. Des relâchements de ces méthodes sont aussi présentés afin de proposer un compromis entre performances et qualité du résultat. La deuxième partie concerne une contrainte utilisée dans les problèmes multi-objectifs : la contrainte Pareto. Dans ce type de problème où aucun objectif n'est plus important qu'un autre, il est commun de vouloir obtenir un ensemble de solutions dites Pareto optimales. Il est possible d'obtenir cet ensemble en intégrant la contrainte Pareto au modèle du problème. Actuellement, cette contrainte utilise une liste pour appliquer son filtrage. Nous proposons d'une part d'améliorer la méthode générale et d'autre part d'utiliser un MDD à la place de la liste pour cette contrainte. Les résultats expérimentaux donnés valident notre approche.