Reproduction de : Habilitation à driger des recherches : Sciences mathématiques. Informatique : Lille 1 : 2005. / N° d'ordre (Lille 1) : 476. Titre provenant de la page de titre du document numérisé. Bibliogr. p. 99-107. Liste des publications.

Reproduction de : Thèse de doctorat : Automatique et informatique industrielle : Villeneuve d'Ascq, Ecole centrale de Lille : 2006. / Titre provenant de la page de titre du document numérisé. Bibliogr. p. 183-194. Index.

Reproduction de : Thèse de doctorat : Automatique et Informatique industrielle : Lille 1 : 2004. / N° d'ordre (Lille 1) : 3510. Résumé en français et en anglais. Titre provenant de la page de titre du document numérisé. Bibliogr. f. 142-158. Liste des publications.

Cette thèse s'inscrit dans le domaine de l'optimisation combinatoire. Elle utilise l'approche polyèdrale pour résoudre des problèmes combinatoires qui se posent dans le contexte des réseaux de télécommunications. Nous introduisons et étudions le problème de synthèse de réseaux à composantes connexes unicycliques. Après avoir rappelé que le problème est facile à résoudre en absence d'autres contraintes, nous étudions de nouvelles variantes en intégrant de nouvelles contraintes techniques. Nous commençons par une contrainte portant sur la taille des cycles. Nous souhaitons interdire tous les cycles contenant au plus $p$ sommets. Le problème est alors NP-Difficile. Des inégalités valides sont alors proposées pour ce problème. On montre sous des conditions bien précises que ces inégalités peuvent être des facettes. Plusieurs algorithmes polynomiaux ont été proposés pour la séparation des inégalités valides. Ces algorithme sont mis en oeuvre et des résultats numériques sont donnés. Nous nous focalisons par la suite sur un nouveau problème dit de Steiner consistant à partitionner un réseau en composantes unicycliques tout en imposant que certains sommets soient sur les cycles. On montre alors que ce problème est facile au sens de la complexité algorithmique en proposant un algorithme polynomial et une formulation étendue du problème. On présente également une description partielle de l'enveloppe convexe des vecteurs d'incidence de ces réseaux. La séparation des inégalités est également étudiée. Nous proposons notamment une généralisation de l'algorithme de Padberg-Rao pour séparer les inégalités Blossom. D'autres contraintes techniques sont prises en compte : contraintes de degrés, contrainte sur le nombre de composantes connexes, appartenance de certains sommets à une même composante connexe et enfin la séparation de certains sommets qui doivent être sur des composantes différentes. Enfin, nous faisons une étude spectrale de deux classes spécifiques de graphes unicycliques.

Résoudre un problème d'ordonnancement consiste à organiser un ensemble de tâches, c'est-à-dire déterminer leurs dates de début et de fin et leur attribuer des ressources en respectant certaines contraintes. Dans cette thèse, nous proposons de nouvelles approches exactes basées sur la programmation par contraintes pour deux classes de problèmes d'ordonnancement NP-difficiles validées expérimentalement par l'implémentation d'un ensemble de nouvelles fonctionnalités dans le solveur de contraintes choco. Dans un problème d'atelier, n lots sont constitués chacun de m tâches à exécuter sur m machines distinctes. Chaque machine ne peut exécuter qu'une tâche à la fois. La nature des contraintes liant les tâches d'un même lot peut varier (séquencement global ou par lot, pas de séquencement). Le critère d'optimalité étudié est la minimisation du délai total. Nous proposons d'abord une étude et une classification des différents modèles et algorithmes de résolution. Ensuite, nous introduisons une nouvelle approche flexible pour ces problèmes classiques. Une machine à traitement par fournées peut traiter plusieurs tâches en une seule opération, une fournée. Les dates de début et de fin des tâches d'une même fournée sont identiques. Le problème étudié consiste à minimiser le retard algébrique maximal de n tâches de différentes tailles sur une machine de capacité b. Conjointement, la somme des tailles des tâches d'une fournée ne doit pas excéder la capacité b. Nous proposons, dans ce contexte, un modèle basé sur une décomposition du problème. Nous définissons ensuite une nouvelle contrainte pour l'optimisation basée sur une relaxation du problème qui améliore sa résolution.

Nous détaillons dans cette thèse des algorithmes modérément exponentiels pour l'approximation du problème MAX SAT. Nous discutons d'une méthode générique pour la conception d'algorithmes exponentiels réalisant des schémas d'approximation dans un cadre plus général. Enfin, nous présentons des résultats paramétrés pour des problèmes de coupe à cardinalité contrainte.

Dans cette thèse, différents problèmes de la combinatoire des mots et de géométrie discrète sont considérés. Nous étudions d'abord l'occurrence des palindromes dans les codages de rotations, une famille de mots incluant entre autres les mots sturmiens et les suites de Rote. En particulier, nous démontrons que ces mots sont pleins, c'est-à-dire qu'ils réalisent la complexité palindromique maximale. Ensuite, nous étudions une nouvelle famille de mots, appelés mots pseudostandards généralisés, qui sont générés à l'aide d'un opérateur appelé clôture pseudopalindromique itérée. Nous présentons entre autres une généralisation d'une formule décrite par Justin qui permet de générer de façon linéaire et optimale un mot pseudostandard généralisé. L'objet central, le f-palindrome ou pseudopalindrome est un indicateur des symétries présentes dans les objets géométriques. Dans les derniers chapitres, nous nous concentrons davantage sur des problèmes de nature géométrique. Plus précisément, nous don-nons la solution à deux conjectures de Provençal concernant les pavages par translation, en exploitant la présence de palindromes et de périodicité locale dans les mots de contour. À la fin de plusieurs chapitres, différents problèmes ouverts et conjectures sont brièvement présentés.

Le travail présenté dans cette thèse traite des problèmes d'affectation de fréquences (FAP) qui se produisent dans les systèmes de communication par satellite utilisant la technologie SDMA. Ces systèmes se composent d'un satellite et d'une zone de service de taille fixe dans laquelle sont répartis des utilisateurs. L'objectif est alors de servir un maximum d'utilisateur en fréquence dans cette zone de service. Cependant, l'affectation ne doit pas violer les contraintes d'interférence qui apparaissent lorsque deux utilisateurs utilisent une même fréquence ou lorsqu'ils se partagent une même plage de fréquence. Deux types d'interférences sont considérés dans cette étude : les interférences binaire et cumulative. Pour chacune d'elles, les problèmes d'affectation de fréquence de type mono-porteuse (une fréquence par utilisateur) et multi-porteuses (plusieurs fréquences par utilisateur) sont traités. Le problème de l'affectation bidimensionnelle est aussi abordé et nous proposons des modèles de Programmation Linéaire en Nombre Entiers (PLNE) pour le résoudre. Au niveau des méthodes de résolution, nous utilisons des algorithmes gloutons, des modèles de PLNE pour le problème de type mono-porteuse. En outre, un algorithme de déplacement continu de faisceau est conçu pour améliorer les solutions en résolvant un problème d'optimisation continu non linéaire. Concernant le problème de type multi-porteuses, nous le ramenons à un problème d'ordonnancement et celui-ci est résolu à l'aide de la PLNE et la Programmation Par Contraintes (PPC). Il est par ailleurs montré que les résultats issus de la PPC sont meilleurs que ceux de la PLNE. De plus, en transformant les interférences cumulatives en interférences binaires, la méthode d'ordonnancement avec les contraintes induites par les cliques donne de bien meilleurs résultats. Nous considérons également un problème industriel dans lequel de nombreuses contraintes apparaissent ce qui rend le problème très complexe et insoluble avec des méthodes exactes. Face à ce constat, deux algorithmes gloutons sont réalisés et leurs résultats sont comparés.

Cette thèse porte sur des problèmes d'exploration de données avec le point de vue de la recherche opérationnelle. L'exploration de données consiste en l'apprentissage de nouvelles connaissances à partir d'observations contenues dans une base de données. La nature des problèmes rencontrés dans ce domaine est proche de celle des problèmes de la recherche opérationnelle: grandes instances, objectifs complexes et difficulté algorithmique. L'exploration de données peut aussi se modéliser comme un problème d'optimisation avec un objectif partiellement connu. Cette thèse se divise en deux parties. La première est une introduction à l'exploration de données. Elle présente l'Analyse Combinatoire de Données (ACD), une méthode d'exploration de données issue de l'optimisation discrète. Cette méthode est appliquée à des données médicales originales et une extension aux problèmes d'analyse de temps de survie est proposée. L'analyse de temps de survie consiste à modéliser le temps avant un événement (typiquement un décès ou une rechute). Les heuristiques proposées utilisent des techniques classiques de recherche opérationnelle telles que la programmation linéaire en nombres entiers, la décomposition de problème, des algorithmes gloutons. La seconde partie est plus théorique et s'intéresse à deux problèmes combinatoires rencontrés dans le domaine de l'exploration de données. Le premier est un problème de partitionnement de graphes en sous-graphes denses pour l'apprentissage non supervisé. Nous montrons la complexité algorithmique de ce problème et nous proposons un algorithme polynomial basé sur la programmation dynamique lorsque le graphe est un arbre. Cet algorithme repose sur des résultats de la théorie des couplages. Le second problème est une généralisation des problèmes de couverture par les tests pour la sélection d'attributs. Les lignes d'une matrice sont coloriées en deux couleurs. L'objectif est de trouver un sous-ensemble minimum de colonnes tel que toute paire de lignes avec des couleurs différentes restent distinctes lorsque la matrice est restreinte au sous-ensemble de colonnes. Nous montrons des résultats de complexité ainsi que des bornes serrées sur la taille des solutions optimales pour différentes structures de matrices.

La cohabitation de plusieurs services différents sur un même réseau soulève de nombreux problèmes pour la gestion et la conception de réseau de télécommunication. L'introduction de mécanismes "intelligents " dans les réseaux multiservices permet de surmonter la difficulté de mettre en place des méthodes plus traditionnelles pour prendre en compte toute la complexité générée par la multiplication des services. Dans ce contexte, nous nous intéressons au problème de l'évaluation de performance dans les réseaux à l'état stationnaire, et plus spécifiquement l'évaluation des critères de qualité de service (QoS). Au lieu d'essayer de modéliser tous les mécanismes d'un routeur pour formaliser certains critères de QoS, nous proposons d'utiliser les capacités d'apprentissage et de généralisation des réseaux de neurones pour apprendre cette QoS à partir d'observations du système. Nous proposons ainsi des modèles neuro-mimétiques de différents critères de la QoS d'un noeud du réseau qui s'appuient sur une description statistique relativement simple des trafics incidents. Nous avons étudié l'apprentissage de plusieurs critères de qualité de service à partir de simulations à évènements discrets dans le cas de files d'attente élémentaires et de files d'attente à serveur partagé qui modélisent la différentiation de services dans les routeurs IP ou MPLS. Nous généralisons ensuite cette approche pour effectuer l'estimation de la QoS le long d'un chemin et proposons pour cela une coopération distribuée de modèles neuronaux. Les réseaux de neurones sont chargés d'estimer à la fois les critères de qualité de service et une description du trafic de sortie. Ce schéma couplé à un protocole de type RSVP permettrait à terme de propager les estimations le long du chemin pour établir une estimation de la QoS de bout en bout. Nous nous intéressons enfin au problème de routage optimal sous contraintes de QoS de bout en bout. Nous présentons une formalisation multiflot permettant de mettre en place une stratégie de résolution de type déviation de flot qui s'appuie sur une approche de type lagrangien augmenté pour relâcher les contraintes de QoS. Cette stratégie permet d'obtenir un optimum local réalisable. Nous proposons ensuite de remplacer l'approximation M/M/1 traditionnellement utilisée dans les modèles de multiflot par un modèle par réseaux de neurones de la QoS, plus réaliste notamment dans le cas de la différentiation de service. Toutefois il est nécessaire de garantir la croissance des fonctions évaluations pour assurer la validité du schéma d'optimisation. Cette monotonie peut être imposée lors de l'apprentissage du modèle neuronal par l'ajout de contraintes sur les dérivées premières. Nous avons développé ainsi un algorithme d'apprentissage sous contraintes qui impose la monotonie dans les réseaux de neurones feed-forward en utilisant des méthodes classiques de l'optimisation nonlinéaire sous contraintes.