Après un rappel succinct du problème d'ordonnancement PERT classique, on étudie les relations entre la criticité et les marges dans les problèmes où les durées des différentes tâches du projet sont représentées par des intervalles nets. Nous exposons ensuite de nouveaux algorithmes de calcul des dates de début au plus tard et des marges pour ces problèmes, basés sur la topologie du problème considéré, et l'annalyse de sous-chemin critique dans le graphe associé.

Ces algorithmes ont été testés sur des bibliothèques de problèmes d'ordonnancement réalistes, afin de valider leur intérêt d'un point de vue computationel, car cet aspect dépend de la forme du graphe associé au problème considéré.

Nous nous intéressons dans la suite aux problèmes d'ordonnancement où les durées des tâches sont représentées par des intervalles flous. Nous introduisons une nouvelle façon d'effectuer des calculs sur les intervalles flous avant de l'appliquer à notre problème d'ordonnancement afin de calculer les dates de début au plus tard et les marges floues du problème.

La conception de réseaux est un sujet d'optimisation toujours très actif, particulièrement dans le monde des télécommunications. Ces problèmes industriels sont souvent apparentés à des problèmes de flots et de multiflots sur lesquels se greffent de nombreuses contraintes additionnelles. On se penchera sur un problème de dimensionnement qui relève d'un problème de multiflots (multi-commodity network flow problem) dans sa version monorouté (mono-path) avec 6 catégories de contraintes additionnelles.

L'objectif de ce travail est de proposer trois techniques distinctes relevant de l'hybridation pour améliorer la résolution de ces problèmes. La première s'appuie sur l'utilisation d'une contrainte redondante encapsulant un algorithme issu de la Recherche Opérationnelle : le Flot. La deuxième fera appel au concept de contrainte globale d'optimisation utilisant un solveur linéaire. La troisième présentera les résultats obtenus par la relaxation Lagrangienne du problème. Nous mettrons ainsi en avant les mécanismes d'évaluation, de filtrage et de détection de contradiction vis-à-vis du coût, fournis par ces différentes approches.

On s'intéresse au problème d'évaluer la similaritéde deux graphes. En effet, de nombreuses applications nécessitent de mesurer la similarité d'objets, i.e., d'identifier et de quantifier leurs points communs et leurs différences. Lorsque ces objets sont représentés par des graphes, le calcul de cette similarité se ramène à un problème de recherche d'un « meilleur » appariement de graphes, i.e., un appariement des sommets des deux graphes qui maximise leurs points communs. Les mesures de similarité de graphes existantes présupposent que ce meilleur appariement est univoque, i.e., que chaque sommet n'est apparié qu'à au plus un autre sommet. Cependant, certaines applications nécessitent des mesures de similarité basées sur des appariements de graphes multivoques, i.e., des appariements où chaque sommet peut être apparié à plusieurs autres sommets. Ainsi, nous proposons une mesure de similarité de graphes basée sur la notion de « meilleur » appariement multivoque de deux graphes et nous resituons cette mesure par rapport aux notions d'isomorphisme de sous-graphe et de plus grand sous-graphe commun.

Nous montrons ensuite que le calcul de cette similarité est un problème d'optimisation multi-critères. Nous proposons deux modélisations de ce problème et discutons de leur adéquation aux méthodes utilisées pour la résolution de ce problème. Nous discutons enfin de la résolution pratique de notre problème en présentant une approche de résolution complète inspirée de la programmation par contraintes et deux approches de résolution incomplètes traditionnellement utilisées en recherche opérationnelle : une approche gloutonne et une recherche taboue réactive ou la recherche locale est guidée par une liste taboue dont la taille varie en fonction du besoin d'intensification et de diversification de la recherche.

L'objectif de cette présentation est de décrire une approche pour aborder la problématique induite par la nature hybride (statique + dynamique) des systèmes. Un problème combinatoire avec des contraintes liées à la dynamique peut être modélisé par un solveur des contraintes en introduisant des contraintes globales basees sur la theorie de la viabilite. L'opérateur du noyau de viabilite d'un systeme dynamique peut être naturellement introduit dans un systeme des contraintes et les algorithmes de calcul du noyau de viabilité peuvent etre basés sur la théorie des graphes. En conclusion, on montrera une application de notre approche pour un problème du contrôle de trafic aerien et le modèle combinatoire simplifié correspondant.

La résolution de systèmes non-linéaires sur les réels est basée sur des algorithmes de recherche et de filtrage qui combinent des techniques de bissection, des consistances locales et des techniques de calcul sur les intervalles.

Nous présentons d'abord une nouvelle contrainte globale, nommée Quad, qui travaille sur une approximation linéaire précise et correcte des contraintes quadratiques. Puis, nous généralisons l'approche de Quad pour le traitement de systèmes non-linéaires quelconques. Différentes techniques de relaxation sont étudiées pour limiter le nombre de nouvelles contraintes générées. La résolution globale des contraintes linéaires est effectuée à l'aide du simplexe. Nous présentons une procédure pour le calcul de cooeficients corrects pour les équations linéaires générées ainsi que pour le calcul rigoureux des bornes avec le simplexe.

Un nouvel algorithme qui combine ces contraintes globales avec des filtrages locaux (comme la Box-consitence) et des méthodes de calcul par intervalles est proposé. Cet algorithme a été évalué sur un ensemble de benchmarks qui portent sur des problèmes de cinématique, mécanique et de robotique.

Sur ces problèmes, ce nouvel algorithme surpasse largement les méthodes de calcul par intervalles et les systèmes de programmation par contraintes. De plus, les résultats obtenus se comparent de manière avantageuse avec ceux des meilleurs outils d'optimisation actuellement disponibles.

Dans [JL02], N. Jussien et O. Lhomme ont introduit une nouvelle classe d'algorithmes de résolution d'instances de CSP, qui combinent intimement recherche locale sur des affectations partielles et propagation de contraintes à partir de ces affectations partielles. Dans cet exposé nous rendrons compte d'une étude expérimentale menée dans le cadre d'un DEA, visant (i) à établir la liste des paramètres qui interviennent dans la définition d'algorithmes de cette classe (mécanisme de propagation, variables et valeurs sur lesquelles portent la propagation, mémorisation de justifications d'effacement, utilisation de l'ordre d'affectation, heuristiques de choix des variables à affecter ou à désaffecter, mécanismes d'exploration des domaines, ... ) (ii) à déterminer les combinaisons de valeurs de ces paramètres qui conduisent aux algorithmes les plus efficaces. Incidemment, nous rendrons compte de résultats expérimentaux montrant la capacité de cette classe d'algorithmes incomplets à prouver l'incohérence d'un très grand nombre d'instances, même autour du pic de complexité.