Soutenance de thèse de Steve MALALEL
par BUTEL Nathalie
Steve MALALEL, soutiendra sa thèse le mardi 25 novembre 2025 à 14h dans la salle 007 du laboratoire i3S (Les Algorithmes, bât. Euclide B).
La thèse intitulée « Algorithmes de filtrage pour contraintes stochastiques et multi-objectif » a été réalisée dans le pôle MDSC, sous la co-direction de Jean-Charles RÉGIN et Marie PELLEAU.
La présentation sera en anglais.
Résumé :
De nombreux problèmes réels peuvent être représentés comme des problèmes combinatoires où trouver une solution revient à trouver une combinaison de valeurs tout en respectant des contraintes définies. Il y a deux manières de résoudre ces problèmes : soit une méthode spécifique au problème est développée, soit un « solveur » général est utilisé. Parmi les solveurs, on retrouve ceux utilisant la programmation par contraintes. Ceux-ci impliquent différents mécanismes afin de résoudre les problèmes efficacement, dont le filtrage qui permet de supprimer des possibilités qui ne satisfont pas certaines contraintes du problème. 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 souvent utilisées dans les problèmes stochastiques ou ayant plusieurs objectifs à optimiser. Les méthodes proposées se basent sur l'utilisation des Diagrammes de Décision Multivalués (MDD). La première partie se concentre sur l'utilisation des MDD pour représenter les tuples de la 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. Nous montrons que la construction d'un MDD représentant les solutions d'une telle contrainte soulève certains problèmes et proposons différentes méthodes afin de les surmonter et garantir des propriétés importantes. La deuxième partie concerne la contrainte Pareto. Pour les problèmes multi-objectifs, il est commun de vouloir obtenir un ensemble de solutions dîtes Pareto optimales, ce que permet la contrainte Pareto. 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.