Le polyèdre associé à un problème d'optimisation combinatoire est l'enveloppe convexe des (vecteurs d'incidence des) solutions réalisables de ce problème. De nombreux problèmes d'optimisation combinatoire se formulent comme une maximisation de fonctions linéaires sur les polyèdres qui leurs sont associés. La description du polyèdre par un système d'inéquations linéaires est intimement liée à la résolution du problème correspondant, par le biais de la programmation linéaire. Afin de déterminer un tel système, une approche classique consiste à décomposer le problème en sous-problèmes tels que les polyèdres associés soient connus ; une composition ultérieure de ces derniers conduit à une description du polyèdre associé au problème considéré. L'objet principal de cette thèse est l'étude de la composition des polyèdres. Dans un premier temps, une approche de composition, basée sur la programmation dynamique et les méthodes de projection polyédrale, est étudiée et des résultats généraux sont proposés, permettant ainsi d'unifier des recherches existantes dans ce domaine. Cette approche est, ensuite, appliquée à la composition de polyèdres associés au problème du voyageur de commerce. En seconde partie, considérant le problème du stable, des opérations sur les graphes (composition par identification de sous-graphes de deux graphes donnés, adjonction d'une nouvelle arête) sont traitées. Des résultats polyédraux sont donc donnés, et des conséquences concernant la perfection et la h-perfection des graphes sont montrés

Après une description de la méthode de Karmarkar, il est montré que la valeur du pas de déplacement peut être largement améliorée. Les principales difficultés pratiques de la méthode sont discutées. Plus particulièrement, l'hypothèse de connaitre, au départ, la valeur optimale de l'objectif. Diverses extensions et variantes sont étudiées dans le but de relaxer l'hypothèse ci-dessus

Ce travail est compose de deux parties. La première concerne l'étude des méthodes d'optimisation convexe à la résolution numérique des problèmes d'optimisation en analyse des données (problème de régression isotone et celui de régression concave). Selon différentes approches et via la théorie de la dualité, nous avons proposé trois méthodes pour résoudre ces problèmes. 1) méthode de l'inverse partiel. 2) méthode du gradient conjugue. 3) méthode de pivotage complémentaire de Lemke. Des résultats numériques sont présentés. Dans la seconde partie, nous proposons une étude synthétique de toutes les méthode de projection dont on dispose actuellement. Nous avons établi les relations qui les lient aux méthodes du type sous-gradients

Aujourd'hui, le fait que la mémoire constitue un goulot d'étranglement pour les performances des programmes est un truisme. Les compilateurs doivent donc optimiser les programmes afin d'éviter de recourir à la mémoire, et ceci en utilisant au mieux les registres disponibles dans le processeur à parallélisme d'instructions (ILP).<br /><br />Cette thèse réexamine le concept de la pression des registres en lui donnant une plus forte priorité par rapport à l'ordonnancement d'instructions, sans ôter à ce dernier ses possibilités d'extraction de parallélisme. Nous proposons de traiter le problème des registres avant la phase d'ordonnancement. Deux grandes stratégies sont étudiées en détail. La première consiste à analyser et manipuler un graphe de dépendance de données (GDD) pour garantir les contraintes de registres sans allonger son chemin critique (si possible). Nous introduisons la notion de saturation en registres qui est la borne exacte maximale du besoin en registres de tout ordonnancement valide, indépendamment des contraintes architecturales. Son but est d'ajouter des arcs au GDD pour que la saturation soit en dessous du nombre de registres disponibles. Réciproquement, la suffisance est le nombre minimal de registres dont il faut disposer pour produire au moins un ordonnancement valide pour le GDD. Si cette suffisance est au dessus du nombre effectif de registres, alors les accès à la mémoire sont inévitables.<br />Notre deuxième stratégie construit une allocation de registres directement dans le GDD en optimisant la perte du parallélisme intrinsèque.<br /><br />Cette thèse considère des blocs de base, des graphes acycliques de flots de contrôles et des boucles internes destinées au pipeline logiciel. Nos expériences montrent que nos heuristiques sont presque optimales. L'étude prouve que nous pouvons et devons traiter les contraintes de registres avant la phase d'ordonnancement tout en garantissant une liberté pour l'extraction et l'exploitation de l'ILP.

Détecter des similarités et des homologies entre protéines est une étape cruciale du processus d'annotation des génomes. Afin de détecter des homologies, les alignements de séquences, globaux ou locaux, sont couramment utilisés. Néanmoins, dans la "zone d'ombre", nous devons utiliser les méthodes de reconnaissance de repliements. Dans ce domaine, le problème du "Protein Threading" (PTP) utilise des paramètres pairés pour aligner globalement une séquence de protéine avec une structure de protéine. À notre connaissance, il n'existe pas de méthode d'alignement local utilisant des paramètres pairés. À partir du PTP, nous proposons cinq modélisations mathématiques de ces alignements locaux qui ont été implémentées et testées grâce au logiciel CPLEX 10.0. Nous avons ensuite développé un algorithme dédié permettant de résoudre un de ces modèles. Cet algorithme utilise des techniques connues en recherche opérationnelle : la séparation-évaluation, la descente de sous-gradient et la relaxation lagrangienne. Bien que les alignements locaux soient d'une plus grande complexité, nous montrons qu'ils sont réalisables et qu'ils améliorent la qualité des alignements.

La première partie de cette thèse, concerne une étude de robustesse des algorithmes de points intérieurs prédicteurs correcteurs, ainsi qu'une approche par décomposition de cette méthode pour la résolution de problè mes de multiflot. Dans la deuxième partie, nous nous intéressons au Problème de Sécurisation Globale dont l'objectif est de déterminer un multiflot (qui transporte toute demande de son noeud origine à son noeud destination en respectant la loi de Kirchhoff) et l'investissement de moindre coût en capacité s nominale et de réserve qui assure le routage nominal et garantit sa survie par reroutage global. Dans notre modèle les routages et les capacités peuvent être fractionnés. PSG se formule alors comme un problème linéaire de grande taille avec plusieurs niveaux de couplage. Sa structure particulière appelle à l'emploi d'algorithmes de décompositions. Nous proposons quatre méthodes utilisant la technique de génération de colonnes. Les deux premières sont basées sur les techniques proximales. Leur tâche principale consiste en la résolution de sous problèmes quadratiques indépendants. Le troisième algorithme s'inspire de l'approche de points intérieurs décrite à la première partie. Pour finir, nous intégrons une procédure d'élimination de chemins dans une adaptation d'un solveur de points intérieurs. Nous reportons des résultats numériques obtenus en testant ces algorithmes sur des données réelles fournies par le CNET.

Cette thèse porte essentiellement sur les problématiques fondamentales d'optimisation combinatoire qui se dégagent de la modélisation structurelle et algorithmique du dimensionnement des réseaux de transport WDM tout-optiques. L'optimisation de ces réseaux est nécessaire aux opérateurs de télécommunication, qui demandent la garantie d'une exploitation efficace des ressources déployées. La thèse est organisée en trois parties. La première partie traite du problème de routage et affectation de longueur d'onde. Nous proposons de résoudre le problème considérant des demandes de trafic permanentes. Des méthodes à la fois exactes basées sur la programmation linéaire et approchées ont été développées. Nous étendons ensuite le modèle de trafic pour considérer simultanément des demandes de trafic pré-planifiées et des demandes de trafic aléatoires. Différent algorithmes de routage ont été développés. Les différents algorithmes ont été comparés en terme de taux de rejet global. La deuxième partie concerne le problème de routage et affectation de longueurs d'onde avec protection. Les ressources dédiées à la protection sont rarement sollicitées, nous cherchons à en minimiser le nombre grâce au multiplexage des circuits optiques de protection. Des méthodes exactes et approchées sont encore une fois proposées considérant les demandes de trafic citées ci-dessus. La dernière partie présente un algorithme de reroutage de canaux optiques afin d'améliorer le taux de rejet dans les réseaux tout-optiques sans convertisseurs en longueurs d'onde. Plusieurs variantes de l'algorithme ont été proposées. Les résultats obtenus montrent un gain intéressant en terme de taux de rejet.

This thesis presents a hybrid decision aid approach for supply networks redesign and planning int the context of multi-site enterprises. This approach is iterative and integrates a mixed integer programming model and a simulation model being at different decisional levels : the mathematical model is a strategic/tactical model and the simulation model is a tactical/operational model. These two models are based on the same modelling of the supply network. First, we describe the elements constituting the decision aid approach. We present two generic mixed integer programming models, multi-product, multi-echelon and multi-period, which search to maximize the profit of the multi-site enterprise. We propose a heuristic approach to solve one of these programs. We describe the developed simulation model. It reproduces the behaviour of the whole supply chain and takes into account the management policies. then, we present the adopted integration methodology. For a problem based on industrial cases, we show that the two models have their role in the decision aid approach and that they contribute both in the search of a good quality network design.

Dans cette thèse, nous nous intéressons principalement à l'étude du fonctionnement cyclique mono-produit des ateliers de traitement de surface. Notre contribution porte sur le problème d'ordonnancement associé connu dans la littérature sous le nom Cyclic Hoist Scheduling Problem (CHSP). L'objet de cette thèse est de proposer des méthodes efficaces pour la résolution des problèmes de traitement de surface dans le cas où les produits à traiter sont du même type. Nous traitons en particulier le cas où le nombre des robots présents sur la ligne est égal à deux, ce qui augmente le nombre des contraintes du problème, sachant que dans le cas mono robot, ce problème a été prouvé NP-Complet. Pour cela, nous proposons une méthode qui combine deux heuristiques et un programme linéaire mixte. Cette méthode permet notamment d'affecter les mouvements de transport à l'un des deux robots tout en gérant les risques de collision entre eux, lorsque la gamme opératoire des produits à traiter suit l'implantation des cuves.Par la suite, nous proposons une extension du modèle au cas de lignes complexes. Enfin, nous étudions le cas d'un fonctionnement mixte, pour lequel il est nécessaire de traiter dans une même installation des produits différents et des rafales de produits identiques. Dans ces conditions, la solution la plus intéressante pour les industriels est de pouvoir alterner des modes de production dynamiques et cycliques. Pour cela, nous proposons une méthode efficace permettant de résoudre le problème d'ordonnancement associé à la phase transitoire relative à ce type de fonctionnement. Elle consiste en particulier à chercher les dates d'entrée au plus tôt des produits. La principale difficulté identifiée consiste ici à passer du mode dynamique au mode cyclique, c'est-à-dire à rejoindre un cycle à partir d'une solution courante donnée, en supposant que ce cycle est connu à priori. Les méthodes élaborées dans les divers cas traités sont validées par des tests sur des benchmarks de la littérature.

Cette thèse s'intéresse au fonctionnement cyclique multi-produits des ateliers de traitement de surface, et au problème d'ordonnancement associé (HSP), caractérisé par des contraintes fortes et atypiques, dont certaines sont liées aux ressources de transport. Dans le cas de productions en grandes séries, une commande cyclique de ces systèmes est particulièrement adaptée, permettant notamment de réduire la combinatoire de résolution, et sous réserve que les ratios de produits soient connus à l'avance. Notre objectif est de trouver le meilleur ordonnancement des tâches de traitement et de transport en un temps raisonnable. Pour cela, nous proposons une première approche, basée sur un modèle linéaire et une méthode de résolution arborescente de type séparation et évaluation. Nous présentons des modélisations pour différentes extensions du problème dit de base et nous fournissons des exemples illustratifs et des résultats sur des benchmarks. Par la suite et compte tenu de l'analyse de la littérature relative aux ordonnancements cycliques mono-produit et multi-produits, nous proposons tout d'abord une heuristique dédiée au cas multi-produits étudié, et basée sur un algorithme de liste. Avec ce dernier, nous obtenons un ordonnancement cyclique dont le degré du cycle n'est pas fixé au préalable. Enfin, nous présentons une deuxième modélisation approchée sous la forme d'un algorithme génétique pour résoudre un HSP 2-cyclique. Ces différents modèles sont validés par des tests sur des benchmarks de la littérature pour lesquels nous avons obtenus des résultats prometteurs. Nous terminons par une analyse critique des avantages et inconvénients des modèles élaborés et par quelques propositions de perspectives pour ce travail.