Dissertations / Theses on the topic 'Méthodes de relaxation (Mathématiques)'
To see the other types of publications on this topic, follow the link: Méthodes de relaxation (Mathématiques).
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Méthodes de relaxation (Mathématiques).'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Liess, Olivier. "Méthodes de décomposition non standard et applications." Avignon, 2006. http://www.theses.fr/2006AVIG0145.
Full text
2
Neto, José. "Développement d'algorithmes de génération de contraintes et extensions." Evry, Institut national des télécommunications, 2006. http://www.theses.fr/2006TELE0003.
Full textAbstract:
Apparus dans les années 50, les algorithmes de génération de contraintes sont aujourd'hui couramment mis en oeuvre dans le cadre de la résolution de problèmes difficiles via la programmation linéaire. Leur principe de base consiste, de manière itérative, à résoudre une relaxation linéaire du problème original, à rechercher une contrainte linéaire valide pour une formulation du problème original et violée par la solution trouvée pour la relaxation courante, puis le cas échéant à ajouter une telle contrainte (voire plusieurs) dans la relaxation courante. Ce processus est réeitéré jusqu'à ce qu'aucune contrainte violée ne soit trouvée pour la solution de la relaxation courante, celle-ci constituant alors une solution optimale du problème original. Nous proposons une modification de ce schéma de résolution au niveau du point de séparation utilisée en vue d’une amélioration des performances, ceci à travers deux approches. Tout d'abord, avec celle intitulée In/Out, il s'agit de définir le point de séparation comme combinaison convexe d’une solution optimale de la relaxation courante et d'une solution réalisable. Des expérimentations numériques sur différents types de problèmes : programmes linéaires générés aléatoirement, dimensionnement de réseaux fiables et problèmes de multiflots, mettent en évidence une nette amélioration potentielle des performances avec de telles procédures. Une autre approche consiste à utiliser plusieurs points dans la phase de séparation. Nous étudions la complexité de ce type de séparation, qui généralise les procédures classiques, de même que celle de problèmes connexes. Notamment, nous établissons l’équivalence polynomiale entre une séparation monopoint classique et la séparation multipoint proposée. Des évaluations préliminaires relatives à cette forme de séparation illustrent intérêts et limites de cette approche. Les deux méthodes introduites : In/Out et multipoint se distinguent des procédures classiques de génération de contraintes essentiellement au niveau des points de séparation utilisés. Une autre façon d'améliorer les méthodes classiques pourrait consister à modifier l’oracle de séparation de manière à favoriser la génération de contraintes particulières. Dans cette thèse nous donnons une caractérisation générale de relaxations ayant même ensemble de solutions optimales que le problème original, conduisant par là même à une évaluation de l’importance des contraintes au sein d’une formulation pour l’obtention d’une solution optimale. Finalement nous rapportons des investigations portées sur le problème de coupe maximum dans un graphe, ceci à deux niveaux. Tout d'abord nous établissons la polynomialité du problèeme de séparation sur des généralisations des familles d’inégalités suspended-tree et path-block-cycle pour certaines valeurs de paramètres fixées. Ensuite nous introduisons et évaluons une procédure originale d’arrondis sur une formulation particulière du problèmeSince they first appeared in the 50's, contraint generation algorithms are now commonly used when solving hard problems through a linear programming approach. In these algorithms, a relaxation of the formulation containing only a subset of the constraints is first solved. Then a separation procedure is called which adds to the relaxation any inequality of the formulation that is violated by the current solution. The process is iterated until no violated inequality can be found. We propose a modification of this resolution scheme at the level of the separation point used in order to improve performance. More precisely, we introduce two approaches. The first one, entitled In/Out, consists in defining the separation point as a convex combination of an optimal solution for the current relaxation, and of a feasible solution. Numerical experiments have been carried out on different problem types : randomly generated linear programs, survivability network design and multicommodity min-cost flow problems, namely. They show evidence of a potential strong improvement of performances with this kind of procedures. Another developed approach consists in using several points in the separation phase. We study the complexity of this kind of separation generalizing classical procedures, and of some other related problems. Namely we establish polynomial equivalence between a classical single-point separation and the multiple-points separation proposed. Preliminary computational experiments for this kind of separation illustrate efficiency of this approach. Both introduced methods : In/Out and multiple-points essentially differ from classical constraint generation procedures at the level of the point being used for separation. Another way to improve traditional schemes would consist in modifying the separation oracle so as to favour the generation of some particular inequalities. In this thesis we give a general characterization of relaxations with the same set of optimal solution as the one for the original problem, thus leading to an evaluation of the “relevance” of constraints present in the formulation used to get an optimal solution. Finally we report investigations on the maximum cut problem, at two levels. First we establish polynomiality of the separation problem for generalizations of two families of inequalities for some fixed parameter values : the so-called suspended-tree and path-block-cycle inequalities. Then, we introduce and evaluate an original rouding procedure applied to a particular formulation of the problem through a divide-and-conquer approach
3
Touati, Nora. "Amélioration des performances du schéma de la génération de colonnes : application aux problèmes de tournées de véhicules." Paris 13, 2008. http://www.theses.fr/2008PA132032.
Full textAbstract:
La génération de colonnes est une méthode dédiée à la résolution de problèmes d'optimisation combinatoire de grande taille. Les méthodes utilisant cette approche de résolution ont souvent des problèmes de convergence, particulièrement quand elles sont utlisées pour résoudre des problèmes pratiques, de grandes dimensions. Nous nous intéressons dans cette thèse à l'accéleration de la méthode de génération de colonnes. Nous proposons des téchniques de diversification pour diminuer le nombre total de colonnes généreés ainsi que le temps de résolution des problèmes maîtres. Nous nous intéressons également à la résolution éfficace des sous-problèmes en utilisant des techniques de réoptimisation, mais aussi en proposant des améliorations de la méthode de programmation dynamique. Les approches sont validées expérimentalement sur le problème de tournées de véhicules avec fénêtre de tempsColumgeneration algorithms are instrumental in many areas of applied optimization where linear programs with an enormous number of variables need to be solued. Although success fully used in many applications, this method suffers from well-known "instability" issues, that somewhat limit its efficiency. This work focuses on accelerating strategies in a column generation algorithm. We propose some diversifiication methods in order to decrease the total number of generated columns and then master problems resolution time. We interest also to solving efficiently the pricing problems, by proposing an improning approch based on reoptimization principle and a new variant of the dynamic programming algorithm. The effectiveness of these approches is validated on vehicule routing problem with time windows
4
Fei, Hongying. "Vers un outil d'aide à la planification et à l'ordonnancement des blocs opératoires." Troyes, 2006. http://www.theses.fr/2006TROY0004.
Full textAbstract:
Dans ce mémoire, nous étudions la gestion des blocs opératoires, et plus particulièrement la planification et l’ordonnancement de ces blocs. Le choix d’études de ce secteur hospitalier est lié au fait qu’il est réputé comme un lieu hautement stratégique dans un établissement hospitalier, surtout en terme de coûts. Il est dès lors utile de s’intéresser à l’optimisation de l’utilisation des ressources hospitalières. Etant donné que l’optimisation du fonctionnement des blocs opératoires est un problème vaste et complexe, nous nous focalisons sur deux sous-problèmes déjà réputés difficiles : la planification et l’ordonnancement des interventions chirurgicales. Ce sont des problèmes centrés sur la programmation opératoire et dont l’objectif est d’obtenir un programme opératoire réalisable et efficace du bloc. Les problèmes de planification sont premièrement formalisés comme des modèles mathématiques en nombres entiers et puis résolus par des procédures heuristiques et par un « Branch-and-Price » basés sur la génération de colonnes qui est utilisée pour résoudre les relaxations linéaires des modèles concernés afin de trouver les bornes inférieures. Les modèles d’ordonnancement sont traités comme des variantes de modèles de « flow shop » hybride à deux étages et résolus par des algorithmes génétiques hybrides. Finalement, nos modèles ont été testés et validés sur un cas réelThis thesis presents our studies on the operating theatre management, especially on the operating theatre planning and scheduling problem in case that this surgical sector is always regarded as the kernel in a hospital in terms of the expenditure. Therefore, it’s necessary to optimize the assignment of hospital resources in the operating theatre. Since this type of problem is extremely complex, we concentrate on just two sub-problems that are also considered difficult ones by researchers: the surgical cases planning and scheduling problem, which aim to made a surgical cases programming with an objective of obtaining a realizable and efficient surgical cases operating schedule. At firth the weekly planning problems of surgical cases are formulated as a mathematical integer programming, and then they are solved by heuristic procedures and Branch-and-Price ones. All these procedures are based on the column generation procedure, which is used to solve the linear relaxation of each model for a lower bound. The scheduling models are treated as variants of hybrid two-stage flow shop problem and are solved by proposed hybrid genetic algorithms. Finally, our models are tested and validated in a real case
5
Loiseau, Irène. "Sur la génération de colonnes en nombres entiers." Paris 13, 2005. http://www.theses.fr/2005PA132018.
Full textAbstract:
Dans les deux premières parties de ce travail nous présentons des méthodes exactes pour la résolution des problèmes de programmation linéaire en nombres entiers avec un très grand nombre de variables. Ces méthodes sont appelées dans la littérature méthodes de "branch-and-price". Pour les cas où les contraintes de problèmes ont tous leurs coefficients égaux à 0ou 1 (colonnes à composantes 0 ou 1), nous développons des coupes géométriques pour l'élimination des colonnes préalablement générées. Ce schéma peut être appliqué à des problèmes sans structure spécifique. Nous faisons aussi unze comparaison entre les relaxations linéaires des différentes formations de problèmes de programmation linéaire en nombre entiers. Nous discutons des difficultés pour choisir les règles de séparation (ie. De branchement dans l'arbre de recherche) à l'intérieur des algorithmes de génération de colonnes. Dans le dernier chapître on fait une synthèse de quelques problèmes de dimensionnement de réseaux de télécommunications composés d'anneaux ainsi que des problèmes de graphes induits. Nous présentons un algorithme de génération de colonnes appliqué à ce type de problème et des résultats expérimentaux sur des instances de petites et moyennes tailles.
6
Worrakitpoonpon, Tirawut. "Relaxation of isolated self-gravitating systems in one and three dimensions." Paris 6, 2011. http://www.theses.fr/2011PA066190.
Full textAbstract:
La gravité newtonienne joue un rôle essentiel dans l'évolution des objets célestes dans l'univers, mais la compréhension des systèmes gérés par celle-ci reste encore limitée. Dans cette thèse nous présentons une étude théorique de la dynamique des systèmes auto-gravitants à une dimension et à trois dimensions. La question centrale que nous abordons, en utilisant extensivement des simulations numériques, est si la mécanique statistique décrit bien leur comportement. A une dimension nous proposons d'étudier principalement deux questions: la relaxation vers équilibre thermique et la relaxation violente vers des état dit ``quasi-stationnaire'' (QSS). La première question considère la relaxation vers un état correspondant à l'équilibre thermique dans l'ensemble micro-canonique ou canonique, où la solution analytique est connue. Nous introduisons des paramètres d'ordre adaptés qui permettent de mettre en évidence cette relaxation. Plus spécifiquement nous observons que le temps caractéristique de cette relaxation est corrélé avec les fluctuations dans l'état quasi-stationnaire et est linéairement proportionnel au nombre de particules, indépendamment de la condition initiale. La deuxième question concerne la relaxation violente à partir de conditions initiales variées, et une comparaison avec la théorie de relaxation violente de Lynden-Bell. Cette théorie décrit avec une bonne approximation les propriétés de ces états quasi-stationnaires proche de la limite ``dégénérée'' ou, plus généralement, quand la relaxation est ``calme''. L'échec de la théorie est corrélé à l'emergence de structure ``core-halo''. Pour terminer nous étudions les mêmes questions sur les systèmes à trois dimensions. Dans le cas général la théorie de Lynden-bell donne, en absence d'une boîte de confinement, une solution de masse infinie. Nous remarquons que la solution est peu sensible à la taille de la boîte proche de la limite dégénéré. Elle peut être comparée aux résultats de simulations numériques pour le cas (plus physique) où le système est ouvert. Dans ce cas nous observons, comme en une dimension, un bon accord avec la prévision théorique dans le régime proche de la limite dégénérée ou autrement l'apparition de structure ``core-halo''
7
Largeron, Christine. "Reconnaissance de formes par relaxation : un modèle d'aide à la décision." Lyon 1, 1990. http://www.theses.fr/1990LYO10256.
Full textAbstract:
Des recherches portant d'une part sur la definition et la construction de nouvelles structures de voisinages, et d'autre part sur les techniques de relaxation, nous ont conduits a aborder sous une meme approche les problemes de reconnaissance des formes supervisee et non supervisee. Cette approche repose sur une hypothese de coherence, selon laquelle des elements voisins dans l'ensemble de representation appartiennent le plus souvent a une meme classe, et son objectif est d'exploiter au mieux pour chaque element, l'information contextuelle apportee par son voisinage. Pour le classement, nous definissons un critere global qui tient compte a la fois de la coherence locale et de la fidelite aux observations. L'optimisation de ce critere conduit a un probleme de point fixe dont la resolution par la procedure de gauss-seidel aboutit a un reetiquetage de l'ensemble d'apprentissage. La decision finale est prise a partir de ce nouvel etiquetage. Ce modele permet d'utiliser la regle de decision des plus proches voisins, avec efficacite, lorsque l'ensemble d'apprentissage est de petite taille et contient des individus atypiques; ce qui est souvent le cas en sciences humaines. L'application des memes principes dans le domaine de la classification automatique permet de detecter des zones de forte densite et de construire une partition dont le nombre de classes est determine automatiquement par l'algorithme
8
Ettaouil, Mohamed. "Satisfaction de contraintes non linéaires en variables 0-1 et outils de la programmation quadratique." Paris 13, 1994. http://www.theses.fr/1994PA132006.
Full textAbstract:
Notre travail s'inscrit dans le cadre des études consacrées à la programmation mathématique en nombres entiers. Plus précisément, il concerne la résolution exacte du problème de satisfaction de contraintes non linéaires en variables 0-1. La méthode que nous proposons pour résoudre le problème de satisfaction de contraintes non linéaires a variables bivalentes, se place dans le même ordre d'idée que la méthode fast proposée par Bennaceur et plateau dans le cas linéaire. Elle s'appuie sur la résolution d'une suite de problèmes d'optimisation non linéaires en variables 0-1. Pour résoudre chacun d'eux nous proposons de privilégier les méthodes approchées utilisant les concepts fondamentaux: heuristiques, dualité, réduction et recherche arborescente. L'étude plus spécifique de la programmation quadratique en nombres entiers, a permis de valider la méthode en menant des expériences numériques dans le cadre de la satisfaction de contraintes quadratiques en variables 0-1
9
Bordes, Laurent. "Inférence statistique pour des modèles paramétriques et semi-paramétriques : modèles de l'exponentielle multiple, test du Chi-deux, modèles de vie accélérée." Bordeaux 1, 1996. http://www.theses.fr/1996BOR10649.
Full textAbstract:
Cette these s'articule autour de trois parties. Dans la premiere partie on applique les procedes classiques de l'estimation sans biais avec variance minimale a une loi parametrique exponentielle multidimensionnelle. On s'interesse plus particulierement aux estimateurs des fonctions de repartition dans diverses situations comme par exemple la censure de type ii. Dans la deuxieme partie on aborde la construction de tests d'ajustement du chi-deux. On propose une statistique de test pour le modele exponentiel evoque ci-dessus ; des simulations illustrent le comportement du test suivant que l'on privilegie les estimateurs du maximum de vraisemblance ou les estimateurs sans biais du minimum de variance. On construit une nouvelle statistique de type chi-deux pour des donnees groupees definies comme etant mal observees. Apres avoir obtenu le comportement asymptotique de la statistique dans le cadre d'une hypothese simple, on en donne une illustration par des simulations et on generalise ces resultats au cas d'hypotheses composites. Cette partie s'acheve par une remarque sur la correction de continuite. Dans la derniere partie de cette these, apres avoir decrit plusieurs modeles semi-parametriques de vie acceleree permettant la prise en compte de variables explicatives et generalisant les modeles classiques de l'analyse de survie, on montre comment obtenir des estimateurs des fonctions de survie associees a un modele dit additif ; enfin, par les techniques mathematiques liees aux processus de comptage on obtient des resultats asymptotiques quant aux comportements des estimateurs, dans le cadre de durees de vie censurees a droite et stratifiees
10
Martin, Véronique. "Méthodes de décomposition de domaine de type relaxation d'ondes pour des équations de l'océanographie." Phd thesis, Université Paris-Nord - Paris XIII, 2003. http://tel.archives-ouvertes.fr/tel-00583196.
Full textAbstract:
L'objectif de ce travail est de développer des algorithmes de décomposition de domaine pour des équations de l'océanographie. Les méthodes de décomposition de domaine consistent à décomposer un domaine de calcul de grand taille en plusieurs sous-domaines plus petits. Elles s'appliquaient jusqu'à présent à des problèmes stationnaires, nous généralisons ici ce type de méthodes aux problèmes en temps ('Schwarz Waveform Relaxation Methods'). Le principal but de cette nouvelle approche est de simuler des problèmes multiphysiques pour lesquels il est intéressant d'avoir une discrétisation temporelle différente dans chaque sous-domaine. Nous généralisons aux équations d'évolution une méthode récente qui consiste à écrire les conditions transparentes (Conditions aux Limites Absorbantes) puis les approche par des opérateurs différentiels d'ordre 1 dans la direction normale à l'interface et d'ordre 0 ou 1 dans la direction tangentielle. Nous développons cette méthode premièrement pour l'équation de convection diffusion qui traduit notamment l'advection des traceurs (température, salinité, traceurs passifs) dans l'océan. Nous approchons les opérateurs exacts par développement de Taylor, ou par optimisation du taux de convergence. Nous démontrons que les problèmes aux limites introduits sont bien posés. Puis nous montrons la convergence des algorithmes correspondants. Des résultats numériques sont implémentés dans le cas avec ou sans recouvrement et mettent en évidence la réelle efficacité des méthodes optimisées. Nous faisons ensuite un premier pas vers le couplage d'équations en implémentant un algorithme de couplage de l'équation de convection avec l'équation de convection diffusion. Ensuite nous traitons les équations de Saint Venant, moyennes verticales des équations de Navier-Stokes en milieu tournant. Nous introduisons pour ce système un algorithme de décomposition de domaine avec des conditions d'interface qui s'obtiennent par des considérations physiques. Nous montrons que cet algorithme est bien posé puis nous en démontrons la convergence. Des résultats numériques concluants sont également exposés.
11
Diop, Mouhamed el Moctar. "Planification et conception topologique des réseaux de télécommunications cellulaires." Clermont-Ferrand 2, 2005. http://195.221.120.247/simclient/consultation/binaries/stream.asp?INSTANCE=UCFRSIM&eidmpa=DOCUMENTS_THESES_83.
Full textAbstract:
La thèse porte sur la planification et la conception topologique des réseaux de télécommunications cellulaires. Deux types de modèles sont abordés. Un modèle de synthèse intégrant dans un même problème la détermination des emplacements des équipements, leur connexion et la couverture des zones. Une méthode de décomposition de Benders lui est appliquée pour trouver une solution optimale. Un deuxième modèle de flots a été construit à partir de ce modèle et résolu d'abord par une relaxation Lagrangienne ensuite par une méthode de décomposition mixte
12
Saleh, Khaled. "Analyse et simulation numérique par relaxation d'écoulements diphasiques compressibles : contribution au traitement des phases évanescentes." Paris 6, 2012. https://theses.hal.science/tel-00761099.
Full textAbstract:
Cette thèse s'intéresse au modèle diphasique de Baer-Nunziato. L'objectif de ce travail est de proposer quelques techniques de prise en compte de la disparition de phase, régime occasionnant d'importantes instabilités au niveau du modèle et de sa simulation numérique. Par des méthodes d'analyse et de simulation reposant sur les techniques d'approximation par relaxation à la Suliciu, on montre que dans ces régimes, on peut stabiliser les solutions en introduisant une dissipation de l'entropie totale de mélange. Dans une première approche dite approche Eulerienne directe, la résolution exacte du problème de Riemann pour le système relaxé permet de définir un schéma entropique extrêmement précis, et qui se révèle bien plus économique en terme de coût CPU (à précision donnée) que le schéma classique très simple de Rusanov. De plus, nous montrons que ce schéma permet de simuler avec robustesse des régimes de disparition de phase. Le schéma est développé en 1D puis étendu en 3D et intégré à un prototype de code industriel développé par EDF. La deuxième approche, dite approche par splitting acoustique, propose une séparation des ondes acoustiques rapides et des ondes de transport lentes. L'objectif est d'éviter la résonance due à l'interaction entre ces deux types d'ondes, et de permettre à long terme un traitement implicite de l'acoustique, et explicite du transport. Le schéma, très simple, permet la prise en compte simple de la disparition de phase. La nouveauté est ici l'exploitation de fermetures dissipatives nouvelles du couple vitesse et pression d'interface, qui permettent le contrôle des solutions du problème de Riemann associé à l'étape acoustiqueThis thesis deals with the Baer-Nunziato two-phase flow model. The main objective of this work is to propose some techniques to cope with phase vanishing regimes which produce important instabilities in the model and its numerical simulations. Through analysis and simulation methods using Suliciu relaxation approximations, we prove that in these regimes, the solutions can be stabilised by introducing some extra dissipation of the total mixture entropy. In a first approach, called the Eulerian approach, the exact resolution of the relaxation Riemann problem provides an accurate entropy-satisfying numerical scheme, which turns out to be much more efficient in terms of CPU-cost than the classical and very simple Rusanov's scheme. Moreover, the scheme is proved to handle the vanishing phase regimes with great stability. The scheme, first developed in 1D, is then extended in 3D and implemented in an industrial code developed by EDF. The second approach, called the acoustic splitting approach, considers a separation of fast acoustic waves from slow material waves. The objective is to avoid the resonance due to the interaction between these two types of waves, and to allow an implicit treatment of the acoustics, while material waves are explicitly discretized. The resulting scheme is very simple and allows to deal simply with phase vanishing. The originality of this work is to use new dissipative closure laws for the interfacial velocity and pressure, in order to control the solutions of the Riemann problem associated with the acoustic step, in the phase vanishing regimes
13
Chouai, Sihem. "Calcul tridimensionnel des champs électromagnétiques dans les applicateurs par la méthode de relaxation." Toulouse, INPT, 1998. http://www.theses.fr/1998INPT022H.
Full textAbstract:
Ce travail présente l'élaboration d'un nouveau solveur électromagnétique adapté au chauffage micro-ondes. La méthode développée est issue d'une description de l'espace par éléments finis combinée à une technique de relaxation. L'obtention de la nouvelle solution est fonction des changements apportés à la structure étudiée (changements du type conditions aux limites) durant la procédure de calcul. L'avantage principal de la méthode est la construction immédiate et à faible coût en trois dimensions de schémas explicites du second ordre en espace basés sur des modèles déterministes plus proches de la réalité physique. De nombreux cas tests numériques de validation en trois dimensions y figurent. Nous montrons enfin, l'intérêt que présente notre approche pour suivre d'une manière naturelle, l'évolution dans le temps du couplage thermoélectrique.
14
Cherfi, Nawal. "Méthodes de résolution hybrides pour les problèmes de type knapsack." Paris 1, 2008. http://www.theses.fr/2008PA010056.
Full textAbstract:
Dans cette thèse, nous nous intéressons aux problèmes du knapsack multidimensionnel à choix multiple. Ils interviennent essentiellement en télécommunication. Nous proposons de nouvelles méthodes hybrides de résolution exacte et approchée. Dans un premier temps, nous proposons des méthodes heuristiques en se basant sur les techniques de génération de colonnes et d’arrondi. Ensuite, nous abordons une méthode de recherche locale, dite méthode de branchement local, où des contraintes linéaires sont introduites pour intensifier et diversifier la recherche. Cette méthode est ensuite hybridée avec la génération de colonnes et une technique d’arrondi. Concernant la résolution exacte, nous nous basons sur une méthode de « branch and cut ». Nous commençons par proposer de nouvelles contraintes valides pour le problème. Ensuite, nous les associons à des contraintes de couverture locales et globales.
15
Drullion, Frédérique. "Définition et étude de systèmes linéaires pour la simulation d'écoulements et l'optimisation de formes aérodynamiques par méthode de gradient." Bordeaux 1, 2004. http://www.theses.fr/2004BOR12898.
Full textAbstract:
Cette thèse présente l'étude des systèmes linéaires issus de l'application de schéma backward-Euler pour la résolution des équations RANS complétées par le modèle de turbulence k-? d'une part, et pour la résolution des équations linearisée et adjointe qui interviennent dans le processus d'optimisation par méthode de gradients. La résolution de ces systèmes est critique pour la convergence du schéma, il est donc important de les définir et de les résoudre aussi bien que possible. Pour les équations RANS, dans un premier temps, puis pour les équations linearisée et adjointe, sont exposées et testées différentes propositions visant à accélérer la convergence des schémas, celles-ci portent soit sur le membre de gauche des équations, soit sur la méthode de résolution des systèmes linéaires. L'ensemble de ces propositions est testé sur différents cas test bi-dimensionnels et tridimensionnels, aussi bien pour des écoulements de fluide parfaits que de fluide visqueux et pour des cas d'aérodynamique interne aussi bien qu'externe.
16
Gomes, Cristiana Maria Nascimento. "Radio mesh networks and the round weighting problem." Nice, 2009. http://www.theses.fr/2009NICE4049.
Full textAbstract:
Dans cette thèse, nous étudions le problème joint du routage et de l'attribution des "slots" entre les routeurs et les points d'accès dans les réseaux radio maillés. Nous le modélisons comme un problème de "Round weighting" dont l'objectif est de minimiser la période d'activation des "slots" en assurant une capacité suffisante pour répondre aux demandes de bande passante des routeurs. Résoudre le problème dans son intégralité nécessite la génération d'un ensemble exponentiel de "rounds", ce qui est hors de portée même pour des petits réseaux. Par conséquent, nous développons un modèle mathématique multicritère qui résout le problème en utilisant une méthode de génération de colonnes. Nous observons que le goulot d'étranglement est en général situé autour d'un point d'accès. Nous proposons une méthode pour obtenir des bornes inférieures et des bornes supérieures pour les graphes généraux. Nous appliquons ces méthodes aux grilles obtenant des formules closes pour des demandes uniformes et des stratégies optimales de routage pour des demandes non-uniformes. Motivé par les résultats sur l'existence d'une région limitée capable de représenter le réseau dans sa totalité, on considère une variante du RWP qui traite aussi de l'allocation de bande mais en considérant le SINR dans un réseau CDMA. Nous donnons des conditions suffisantes pour qu'un réseau puisse être réduit à un réseau mono-saut autour du point d'accès. Cela est dû au fait que le problème est convexe. Nous nous intéressons aux solutions Pareto-optimales pour lesquelles chaque flot dans le goulot reçoit une partie juste de la bande passante disponibleIn this thesis, we address the joint routing and slot assignment problem in radio mesh access networks between the routers and the gateways. We model the problem as a Round Weighting Problem (RWP) in which the objective is to minimize the overall period of slot activations providing enough capacity to satisfy the bandwidth requirements of the routers. Solving the full problem means generating an exponential set of simultaneous transmission rounds which is intractable even for small networks. To cope with this issue, we implement a mathematical multi-objective model to solve the problem using a column generation method. We observe that the bottleneck is usually located in a limited region around a gateway. We propose a method to obtain lower bounds (considering only a limited probable bottleneck region) and upper bounds for general graphs. Our methods are applied to grid graphs providing closed formulae for the case of uniform demands, and also optimal routing strategies considering non-uniform demands. Motivated by the results of the existence of a limited (bottleneck) region capable of representing the whole network, we consider a variant of the RWP dealing also with bandwidth allocation, but considering SINR conditions in a CDMA network. We give sufficient conditions for the whole network to be reduced to a single-hop around the gateway. It is due to the fact that the problem is convex under some conditions that are often met. We are interested in Pareto-optimal solutions in which each flow going through a bottleneck receives a fair share of the available bandwidth
17
Mellouli, Racem. "Ordonnancement sur machines parallèles avec contraintes d'indisponibilité." Troyes, 2007. http://www.theses.fr/2007TROY0022.
Full textAbstract:
Les travaux de cette thèse sont articulés autour du problème d’ordonnancement sur machines parallèles identiques avec contraintes d’indisponibilité pour la minimisation du flow time. Nous avons étudié trois modèles de ce problème. L’objectif est de proposer des méthodes théoriques d’optimisation qui permettent une résolution efficace. Les approches développées sont variées : des heuristiques qui ont amélioré des méthodes classiques de la littérature, trois types d’approches exactes basées sur la programmation linéaire à variables mixtes, branch-and-bound utilisant différents schémas de séparation et programmation dynamique. Nous avons proposé des bornes inférieures constructives et itératives. Celles basées sur la relaxation lagrangienne étaient combinées avec différents outils de la recherche opérationnelle tels que l méthode de sous-gradient, la programmation dynamique et le splitting des travaux. Une méthode de génération de colonnes a été développée. La résolution des problèmes auxiliaires a été réalisée avec une méthode heuristique et une méthode exacte par programmation dynamique. Par ailleurs, nous avons prouvé des propriétés mathématiques et proposé de nouvelles bornes inférieures pour un modèle traité en littérature. Enfin, nous avons élaboré des analyses de performance au pire pour des méthodes heuristiques et une borne inférieureThis thesis is devoted to parallel machine scheduling with availability constraints for minimizing the flow time. We studied three theoretical models of this problem. The objective is to propose theoretical optimization methods that effectively solve these problems. We develop various approaches. Indeed, we proposed heuristic methods that improved classical methods from literature. Three types of exact approaches were considered : methods based on mixes integer linear programming, branch-and-bound methods using different branching schemes and methods based on dynamic programming. We also proposed constructive and iterative lower bounding schemes. In particular, lower bounds based on Lagrangian relaxation are combined with different tools from operational research, such as the subgradient method, dynamic programming and job splitting. Moreover, a method based on column generation has been developed based on a particular formulation of the problem. Auxiliary problems are solves with a heuristic method and an exact method using the dynamic programming. Furthermore, we proved several mathematical properties and proposed new lower bounds for a model already studied in the literature. Finally, we have studied worst-case performance for simple heuristics and a lower bound
18
MOULET, DOMINIQUE. "Extraction et suivi de contours dans les sequences d'images animees." Nantes, 1990. http://www.theses.fr/1990NANT2016.
Full textAbstract:
Ce memoire de these presente une methode de segmentation et de suivi temporel de sequences d'images. La methode que nous proposons permet d'obtenir d'une part l'ensemble des segmentations spatiales associees a chacune des images de la sequence et, d'autre part, un suivi temporel de points caracteristiques fournis par la segmentation. Le procede de suivi temporel de la segmentation spatiale peut se decomposer en trois grandes phases: la phase de prediction, la phase de mise en correspondance et la phase d'affinage. La phase de prediction permet le calcul d'une prediction de la position de chacun des points caracteristiques dans l'image suivante, position que l'on determine de facon precise lors de la phase de mise en correspondance. Cette mise en correspondance est effectuee de facon hierarchique dans une premiere etape par une procedure deterministe puis, dans une seconde etape, par une methode de relaxation probabiliste. Enfin, lors de la derniere phase qui reste a mettre au point, la segmentation obtenue est ajustee afin de rester en parfaite coherence avec les segmentations precedentes
19
Nardi, Giacomo. "On a characterization of the relaxation of a generalized Willmore functional." Paris 6, 2011. http://www.theses.fr/2011PA066539.
Full textAbstract:
Dans cette thèse on étudie la relaxée d'une fonctionnelle dépendant de la courbure moyenne des ensembles de niveau de la fonction. La relaxation est définie par rapport à la topologie forte de L^1 dans l'espace BV. En dimension deux, on peut exprimer la relaxée comme l'intégrale sur l'ensemble des niveaux de la fonction étudiée d'une énergie calculée sur un recouvrement des frontières essentielles d'ensembles de niveau par une famille limite de courbes. En dimension supérieure, on propose une nouvelle formulation pour le problème en définissant des varifolds associés aux mesures de Young-gradients, appelés Young varifolds. On se ramène ainsi à un problème de minimisation pour une fonctionnelle définie sur une certaine classe de Young varifolds. Grâce aux résultats précédents on peut montrer que cette formulation est appropriée en dimension deux. Toutefois, une caractérisation complète de la relaxée à l'aide des Young varifolds reste un problème ouvert.
20
Labois, Mathieu. "Modélisation des déséquilibres mécaniques dans les écoulements diphasiques : approches par relaxation et par modèle réduit." Aix-Marseille 1, 2008. http://www.theses.fr/2008AIX11039.
Full textAbstract:
Cette thèse porte sur l'utilisation de modèles hyperboliques pour la simulation des écoulements diphasiques compressibles, pour trouver des alternatives au modèle bifluide classique. Nous établissons tout d'abord une hiérarchie des modèles diphasiques, obtenue selon des hypothèses d'équilibres des variables physiques entre chaque phase. L'utilisation de développements de Chapman-Enskog permet de relier entre eux les différents modèles existants. De plus, des modèles prenant en compte de petits déséquilibres physiques sont obtenus par des développements à l'ordre un. La deuxième partie de cette thèse porte sur la simulation des écoulements caractérisés par des déséquilibres de vitesses et des équilibres de pression, que nous modélisons de deux manières différentes. Tout d'abord, un modèle à deux vitesses et deux pressions est utilisé, avec l'application de relaxations des vitesses et pressions à temps finis afin d'obtenir un retour à l'équilibre de ces grandeurs. On propose ensuite un nouveau modèle dissipatif à une vitesse et une pression, où l'apparition de termes du second ordre permet de prendre en compte les déséquilibres de vitesse entre les phases. Une méthode numérique basée sur une approche par pas fractionnaires est développée pour ce modèleThis thesis deals with hyperbolic models for the simulation of compressible two-phase flows, to find alternatives to the classical bifluid model. We first establish a hierarchy of two-phase flow models, obtained according to equilibrium hypothesis between the physical variables of each phase. The use of Chapman-Enskog expansions enables us to link the different existing models to each other. Moreover, models that take into account small physical unbalances are obtained by means of expansion to the order one. The second part of this thesis focuses on the simulation of flows featuring velocity unbalances and pressure balances, in two different ways. First, a two-velocity two-pressure model is used, where non-instantaneous velocity and pressure relaxations are applied so that a balancing of these variables is obtained. A new one-velocity one-pressure dissipative model is then proposed, where the arising of second-order terms enables us to take into account unbalances between the phase velocities. We develop a numerical method based on a fractional step approach for this model
21
Arada, Nadir. "Contrôle optimal d'équations paraboliques avec contraintes sur l'état : relaxation et stabilité." Toulouse 3, 1997. http://www.theses.fr/1997TOU30101.
Full textAbstract:
Cette these est consacree a l'etude des problemes de controle optimal gouvernes par des equations paraboliques semilineaires avec contraintes ponctuelles sur l'etat. Des problemes ou l'etat est une fonction continue bornee sur le cylindre espace-temps mais n'est pas continue jusqu'a la frontiere sont consideres : c'est le cas lorsque le controle est un controle frontiere borne dans une condition de dirichlet ou dans une condition initiale. Pour l'obtention des principes de pontryagin, les difficultes sont ici, la non-separabilite de l'espace dans lequel est posee la contrainte, l'interpretation de l'equation adjointe et l'adaptation des techniques de penalisation. En effet, le multiplicateur associe aux contraintes sur l'etat s'interprete comme une mesure sur le compactifie de stone-cech. En adaptant une approche de diperna et majda, nous prouvons un theoreme de decomposition de ce multiplicateur mesure. Ce theoreme nous permet de definir l'equation adjointe comme une equation parabolique avec second membre a donnees mesures de radon. Nous obtenons de la sorte des conditions d'optimalite nouvelles pour cette classe de problemes. Une deuxieme partie concerne la relaxation des problemes de controle par les mesures de young. Des resultats de relaxation ainsi que des conditions necessaires et suffisantes assurant le caractere propre de la relaxation, sont etablis. L'utilisation d'une methode lagrangienne ou d'une methode de penalisation permet d'obtenir des conditions d'optimalite relaxees. Des conditions de stabilite de la fonction valeur par rapport a des perturbations des contraintes sur l'etat, interviennent pour etablir le caractere propre de la relaxation. D'autres conditions garantissent la qualification des contraintes sur l'etat. La relaxation nous a permis de faire une analyse comparative et synthetique de ces differentes conditions. La derniere partie est consacree a l'approximation numerique d'un probleme de controle relaxe gouverne par une equation elliptique. Une estimation de l'erreur d'approximation d'une mesure de young par un controle standard est etablie. L'equation d'etat est discretisee par une methode d'elements finis et la convergence des problemes discretises vers le probleme relaxe continu est etablie.
22
Detienne, Boris. "Planification et ordonnancement : méthodes de décomposition et génération de coupes." Compiègne, 2007. http://www.theses.fr/2007COMP1683.
Full textAbstract:
Cette thèse de Doctorat consiste en l'étude de deux problèmes de la Recherche Opérationnelle. La première partie porte sur un problème de planification de personnel et présente une borne inférieure par décomposition lagrangienne ainsi que deux méthodes de résolution exacte par décomposition et génération de coupes: une décomposition de Benders, et une méthode basée sur des coupes spécifiques, résolvant des instances de taille réelle. Pour la résolution de problèmes de grande taille correspondant à un horizon de planification de plusieurs semaines, une heuristique taboue est développée. La seconde partie, portant sur le problème de minimisation des pénalités d'avance/retard sur une machine, étudie des bornes inférieures et établit des règles de dominance ainsi que de nouvelles règles d'élimination qui se révèlent particulièrement puissantes pour ce problème, puisqu'elles permettent l'élaboration d'une méthode exacte dominant toutes les approches de la littérature pour ce problèmeThis PhD thesis consists in the study of two problems in Operational Research. In the first part, a lagrangian lower bound is proposed for a particular employee timetabling problem, followed by a Benders decomposition and a specific cut generation process based on an exponential formulation, that allow the solving of real-size instances. For solving bigger instances, a taboo method is developed. The second part is a study of the Single Machine Earliness- Tardiness Problem with general completion costs and release dates. After computational results obtained by different lower bounds, we give several dominance rules, and provide new elimination rules that turn out to be very efficient. Indeed, we develop an exact method dominating all known approaches for this problem
23
Mechti, Redouane. "Contribution à la résolution des problèmes de tournées de véhicules avec fenêtres de temps et composition de flotte." Versailles-St Quentin en Yvelines, 1999. http://www.theses.fr/1999VERS0023.
Full textAbstract:
Nous nous sommes intéressés dans ces travaux à un problème de composition d'une flotte hétérogène de véhicules et la conception des tournées associées respectant des contraintes telles, la capacité des véhicules, les fenêtres de temps chez le client, les temps d'attente, etc. Après description du problème et sa modélisation pour une application particulière à la collecte postale, ainsi que toutes les caractéristiques et difficultés dont il faut tenir compte pendant sa résolution, nous présentons deux méthodes de résolution : une méthode exacte et une autre approchée. La méthode exacte est fondée essentiellement sur les techniques de génération de colonnes avec comme difficulté majeure, la résolution du sous-problème- plus court chemin contraint- pour lequel nous avons élabore un algorithme qui repose sur la programmation dynamique et l'exploration A*. La difficulté des instances traitées nous a poussé à construire une méthode approchée - méthode tabou à voisinage variable - qui repose sur un ensemble de mouvements, locaux et globaux, susceptibles de modifier considérablement la structure de la solution et de pouvoir traiter par conséquent des instances beaucoup plus grandes contrairement à la méthode exacte.
24
Berthe, Paul-Marie. "Méthodes de décomposition de domaine de type relaxation d'ondes optimisées pour l'équation de convection-diffusion instationnaire discrétisée par volumes finis." Thesis, Paris 13, 2013. http://www.theses.fr/2013PA132055.
Full textAbstract:
Dans le contexte du stockage des déchets radioactifs en milieu poreux, nous considérons l’équation de convection-diffusion instationnaire et sa discrétisation par des méthodes numériques. La discontinuité des paramètres physiques et la variabilité des échelles d’espace et de temps conduisent à utiliser des discrétisations différentes en temps et en espace dans différentes régions du domaine. Nous choisissons dans cette thèse le schéma volumes finis en dualité discrète (DDFV) et le schéma de Galerkin Discontinu en temps couplés à une méthode de décomposition de domaine de Schwarz de type relaxation d’ondes optimisées (OSWR), ce qui permet de traiter des maillages espace-temps non conformes. La principale difficulté réside dans l’obtention d’une discrétisation amont du flux convectif qui reste locale à un sous-domaine et telle que le schéma monodomaine soit équivalent au schéma multidomaine. Ces difficultés sont appréhendées d’abord en une dimension d’espace où différentes discrétisations sont étudiées. Le schéma retenu introduit une inconnue hybride sur les interfaces entre cellules. L’idée du décentrage amont par rapport à cette inconnue hybride est reprise en dimension deux d’espace, et adaptée au schéma DDFV. Le caractère bien posé de ce schéma et d’un schéma multidomaine équivalent est montré. Ce dernier est résolu par un algorithme OSWR dont la convergence est prouvée. Les paramètres optimisés des conditions de Robin sont obtenus par l'étude du taux de convergence continu ou discret. Différents cas-tests, dont l’un est inspiré du stockage des déchets nucléaires, illustrent ces résultatsIn the context of nuclear waste repositories, we consider the numerical discretization of the non stationary convection diffusion equation. Discontinuous physical parameters and heterogeneous space and time scales lead us to use different space and time discretizations in different parts of the domain. In this work, we choose the discrete duality finite volume (DDFV) scheme and the discontinuous Galerkin scheme in time, coupled by an optimized Scwharz waveform relaxation (OSWR) domain decomposition method, because this allows the use of non-conforming space-time meshes. The main difficulty lies in finding an upwind discretization of the convective flux which remains local to a sub-domain and such that the multidomain scheme is equivalent to the monodomain one. These difficulties are first dealt with in the one-dimensional context, where different discretizations are studied. The chosen scheme introduces a hybrid unknown on the cell interfaces. The idea of upwinding with respect to this hybrid unknown is extended to the DDFV scheme in the two-dimensional setting. The well-posedness of the scheme and of an equivalent multidomain scheme is shown. The latter is solved by an OSWR algorithm, the convergence of which is proved. The optimized parameters in the Robin transmission conditions are obtained by studying the continuous or discrete convergence rates. Several test-cases, one of which inspired by nuclear waste repositories, illustrate these results
25
Le, Hai Yen. "Approche variationnelle de la fonction rang : relaxation convexe, sous-différentiation généralisée, régularisation-approximation de Moreau." Toulouse 3, 2013. http://thesesups.ups-tlse.fr/1973/.
Full textAbstract:
Dans ce mémoire de these, nous étudions la fonction rang du point de vue variationnel. La raison pour laquelle nous nous intéressons à cette fonction est qu'elle apparaît comme une fonction objectif (ou comme fonction contrainte) dans divers problèmes d'optimisation moderne, par exemple: complétion de matrices, analyse de données statistiques, acquisition parcimonieuse de données, etc. Dans certains cas particuliers, les problèmes de minimisation de la fonction rang peuvent être résolus en utilisant la décomposition en valeurs singulières. Mais, en géneral, les problèmes de minimisation de la fonction rang sont « NP-difficiles ». Nous proposons ici quelques propriétés de la fonction rang du point de vue variationnel: des démonstrations supplémentaires pour son enveloppe convexe fermée (restreinte à des boules spectrales), les expressions des sous-différentiels généralisés et la régularisation-approximation au sens de Moreau. Puis, dans le dernier chapitre, nous revenons sur une notion dont la définition ressemble à celle de la fonction rang, la fonction cp-rangIn this dissertation, we consider the rank function from the variational point of view. The reason why we are interested in this function is that it appears as an objective (or constraint) function in various modern optimization problems, such as: low rank matrix completion, multivariate statistical data analysis, compressed sensing, etc. In some particular cases, the rank minimization problems can be solved by using the singular value decomposition of matrices or can be reduced to the solution of linear systems. But in general, the rank minimization problems is known to be « NP-hard ». We provide here several properties of the rank function from the variational point of view: additional proofs for its closed convex relaxation, the expressions of its generalized subdifferentials and the explicit expression of its Moreau regularization-approximation form. Then, in the last chapter, we revisit a notion whose definition resembles that of the rank, the cp-rank function
26
Zhang, Hanyu. "Méthodes itératives à retard pour architecture massivement parallèles." Thesis, Université Paris-Saclay (ComUE), 2016. http://www.theses.fr/2016SACLC068.
Full textAbstract:
Avec l'avènement de machine parallèles multi-coeurs, de nombreux algorithmes doivent être modifiés ou conçus pour s'adapter à ces architectures. Ces algorithmes consistent pour la plupart à diviser le problème original en plusieurs petits sous-problèmes et à les distribuer sur les différentes unités de calcul disponibles. La résolution de ces petits sous-problèmes peut être exécutée en parallèle, des communications entre les unités de calcul étant indispensables pour assurer la convergence de ces méthodes.Ma thèse propose de nouveaux algorithmes parallèles pour résoudre de grands systèmes linéaires.Les algorithmes proposés sont ici basés sur la méthode du gradient. Deux points fondamentaux de la méthode du gradient sont la direction de descente de la solution approchée et la valeur du pas de descente, qui détermine la modification à effectuer à chaque itération. Nous proposons dans cette thèse de calculer la direction et le pas indépendamment et localement sur chaque unité de calcul, ce qui nécessite moins de synchronisation entre les processeurs, et par suite rend chaque itération simple et plus rapide, et rend son extension dans un contexte asynchrone possible.Avec les paramètres d'échelle appropriés pour le pas des longueurs, la convergence peut être démontrée pour les deux versions synchrone et asynchrone des algorithmes. De nombreux tests numériques illustrent l’efficacité de ces méthodes.L'autre partie de ma thèse propose d'utiliser une méthode d'extrapolation pour accélérer les méthodes itératives classiques avec retard. Bien que les séquences de vecteur générées par des méthodes itératives asynchrones générales classiques ne peut être accélérée, nous sommes en mesure de démontrer que, une fois le modèle de calcul et de communication fixés au cours de l’exécution, la séquence de vecteurs générés peut être accéléré. De nombreux tests numériques illustrent l’efficacité de ces accélérations dans le cas des méthodes avec retardWith the increase of architectures composed of multi-cores, many algorithms need to revisited and be modified to exploit the power of these new architectures. These algorithms divide the original problem into “small pieces” and distribute these pieces to different processors at disposal, thus communications among them are indispensible to assure the convergence. My thesis mainly focus on solving large sparse systems of linear equations in parallel with new methods. These methods are based on the gradient methods. Two key parameters of the gradient methods are descent direction and step-length of descent for each iteration. Our methods compute the directions locally, which requires less synchronization and computation, leading to faster iterations and make easy asynchronization possible. Convergence can be proved in both synchronized or asynchronized cases. Numerical tests demonstrate the efficiency of these methods. The other part of my thesis deal with the acceleration of the vector sequences generated by classical iterative algorithms. Though general chaotic sequences may not be accelerated, it is possible to prove that with any fixed retard pattern, then the generated sequence can be accelerated. Different numerical tests demonstrate its efficiency
27
Servigne, Sylvie. "Base de données géographiques et photos aériennes : de l'appariement à la mise à jour." Lyon, INSA, 1993. http://www.theses.fr/1993ISAL0026.
Full textAbstract:
La mise à jour des bases de données géographiques est de nos jours un problème crucial. Nous présentons ici une méthodologie pour l'automatisation de la détection de modifications et la mise à jour d'informations cadastrales à l'aide de photographies aériennes. Après une analyse des spécificités des données que représentent les photos aériennes. , nous nous attachons à la problématique de la mise en correspondance des données géographiques avec les données issues du traitement d'images appliquée aux photos aériennes numérisées. Notre travail s'est articulé suivant deux mouvements subordonnés à l'évolution des informations produites par le traitement d'images : - tout d'abord, nous proposons une méthode originale d'étiquetage basée sur la relaxation pour l'appariement des arêtes des contours des objets géographiques avec un ensemble de segments épars issus du processus de segmentation, - ensuite, nous définissons une méthode de mise en correspondance d'objets géographiques avec des objets picturaux (zones de texture homogène) résultant du traitement des photo aériennes, afin de détecter les modifications ; Puis nous présentons notre analyse des informations utiles pour l'interprétation des objets photographiques non répertoriés dans la base de données géographique. Enfin, nous apportons des précisions sur les éléments nécessaires à la réalisation d'un système opérationnel complet pour la mise à jour de bases de données géographiques à partir de photos aériennesPresently, to update rapidly geographic databases is a problem. A methodology is presented to automatise the detection of change and the updating of cadastral informations by mean of aerial photos. After the analysis of the aerial specificities, we deal with the matching problem between geographic data (in particularly building) and information coming from image processing on aerial photos. Our work is divided into two parts because of data evolution, produced by the image processing process : - firstly, a labelling method is proposed based on relaxation to match contour segments of geographical objects with segments issued from the segmentation process ; - secondly, a matching method is defined between geographic and pictorial objects (areas of uniform texture from aerial photos) in order to detect changes. We then present an analysis of the interesting information which can help the interpretation of new objects (do not exist in the geographic database). Finally, some elements are given in order to design on operative system for updating geographic databases by means of serial photos
28
Cocquebert, Cédric. "Méthodes de type "Waveform-FAC" pour la résolution numérique de problèmes paraboliques." Aix-Marseille 1, 1997. http://www.theses.fr/1997AIX11032.
Full textAbstract:
Le but de ce travail est de proposer une extension de la methode f. A. C. Pour un probleme parabolique. Les systemes differentiels obtenus sont resolus numeriquement par une methode de type waveform relaxation. L'utilisation de ces deux methodes permet un raffinement localise en espace et en temps et suggere une version simplifiee de moving mesh. L'aspect theorique de la methode est traite de deux manieres :. Dans la version totalement discretisee, en se ramenant a un resultat de la methode f. A. C. Dans le cas elliptique. . Dans la version continue en temps, en utilisant une technique de perturbation. Cette etude theorique est completee par de nombreuses verifications numeriques. L'ensemble des possibilites de la methode est alors exploite pour resoudre numeriquement des problemes non-lineaires de propagation de front (issues de la chimie). Enfin, l'introduction de techniques de waveform relaxation permet une parallelisation de l'algorithme.
29
Chehab, Jean-Paul. "Méthode des inconnues incrémentales : application au calcul des bifurcations." Paris 11, 1993. http://www.theses.fr/1993PA112031.
Full textAbstract:
Ce travail est consacré à l'élaboration de nouveaux schémas numériques en bifurcation. Ils résultent de plusieurs généralisations de la méthode de Marder et Weitzner (mW) à l'aide de la méthode des inconnues incrémentales introduite par R. Temam. Nous rappelons tout d'abord la construction et les principales propriétés des inconnues incrémentales d'ordre deux en dimension et un et deux d'espace. Le problème de Poisson donne une première illustration numérique des avantages de la nouvelle technique et nous proposons une famille de pré conditionneurs des matrices sous-jacentes. Ensuite, nous présentons l'algorithme de Marder et Weitzner (mW) qui est bien adapté au calcul de solutions instables. Nous construisons trois types de méthodes incrémentales. Elles sont basées sur une généralisation de la notion de relaxation et généralement mW dans des directions difficilement atteignables avec les techniques de discrétisation classiques. Les différents tests numériques portent sur le calcul de solutions instables de problèmes aux valeurs propres non linéaires. Les comparaisons avec la méthode usuelle de mW mettent en évidence une plus grande vitesse de convergence et un gain de temps cpu important
30
Solay, Rakotonirainy Georges. "Un coup d'œil non standard sur un problème de Zermelo." Nice, 1986. http://www.theses.fr/1986NICE4080.
Full textAbstract:
Dans cette thèse, nous nous sommes attachés à montrer qu'il est possible de faire une théorie complète de l'existence d'un contrôle optimal sans introduire un seul espace fonctionnel, et sans acrobatie particulière. Nous faisons l'exposé dans le cas particulier du contrôle en temps minimum qui est le plus ennuyeux dans l'étude classique : en effet, soit on décide par un changement de variable de tout ramener à un intervalle de temps fixe une fois pour toutes, mais alors on ne peut plus faire l'hypothèse avantageuse de la compacité de l'espace des contrôles, soit on garde des intervalles de temps non fixes, ce qui complique les définitions, les espaces fonctionnels usuels ne pouvant être pris tels quels. Pour nous, ces difficultés n'existent plus et nous limiter à ce cas nous permet de conserver une rédaction courte, notre but n'étant pas d'écrire un ouvrage de théorie de contrôle mais de montrer ce que peut apporter l'emploi de l'analyse non standard dans un domaine classique.
31
Wang, Guanglei. "Relaxations in mixed-integer quadratically constrained programming and robust programming." Electronic Thesis or Diss., Evry, Institut national des télécommunications, 2016. http://www.theses.fr/2016TELE0026.
Full textAbstract:
De nombreux problèmes de la vie réelle sont exprimés sous la forme de décisions à prendre à l’aide de l’information accessible dans le but d’atteindre certains objectifs. La programmation numérique a prouvé être un outil efficace pour modéliser et résoudre une grande variété de problèmes de ce type. Cependant, de nombreux problèmes en apparence faciles sont encore durs à résoudre. Et même des problèmes faciles de programmation linéaire deviennent durs avec l’incertitude de l’information disponible. Motivés par un problème de télécommunication où l’on doit associer des machines virtuelles à des serveurs tout en minimisant les coûts, nous avons employé plusieurs outils de programmation mathématique dans le but de résoudre efficacement le problème, et développé de nouveaux outils pour des problèmes plus généraux. Dans l’ensemble, résumons les principaux résultats de cette thèse comme suit. Une formulation exacte et plusieurs reformulations pour le problème d’affectation de machines virtuelles dans le cloud sont données. Nous utilisons plusieurs inégalités valides pour renforcer la formulation exacte, accélérant ainsi l’algorithme de résolution de manière significative. Nous donnons en outre un résultat géométrique sur la qualité de la borne lagrangienne montrant qu’elle est généralement beaucoup plus forte que la borne de la relaxation continue. Une hiérarchie de relaxation est également proposée en considérant une séquence de couverture de l’ensemble de la demande. Ensuite, nous introduisons une nouvelle formulation induite par les symétries du problème. Cette formulation permet de réduire considérablement le nombre de termes bilinéaires dans le modèle, et comme prévu, semble plus efficace que les modèles précédents. Deux approches sont développées pour la construction d’enveloppes convexes et concaves pour l’optimisation bilinéaire sur un hypercube. Nous établissons plusieurs connexions théoriques entre différentes techniques et nous discutons d’autres extensions possibles. Nous montrons que deux variantes de formulations pour approcher l’enveloppe convexe des fonctions bilinéaires sont équivalentes. Nous introduisons un nouveau paradigme sur les problèmes linéaires généraux avec des paramètres incertains. Nous proposons une hiérarchie convergente de problèmes d’optimisation robuste – approche robuste multipolaire, qui généralise les notions de robustesse statique, de robustesse d’affinement ajustable, et de robustesse entièrement ajustable. En outre, nous montrons que l’approche multipolaire peut générer une séquence de bornes supérieures et une séquence de bornes inférieures en même temps et les deux séquences convergent vers la valeur robuste des FARC sous certaines hypothèses modéréesMany real life problems are characterized by making decisions with current information to achieve certain objectives. Mathematical programming has been developed as a successful tool to model and solve a wide range of such problems. However, many seemingly easy problems remain challenging. And some easy problems such as linear programs can be difficult in the face of uncertainty. Motivated by a telecommunication problem where assignment decisions have to be made such that the cloud virtual machines are assigned to servers in a minimum-cost way, we employ several mathematical programming tools to solve the problem efficiently and develop new tools for general theoretical problems. In brief, our work can be summarized as follows. We provide an exact formulation and several reformulations on the cloud virtual machine assignment problem. Then several valid inequalities are used to strengthen the exact formulation, thereby accelerating the solution procedure significantly. In addition, an effective Lagrangian decomposition is proposed. We show that, the bounds providedby the proposed Lagrangian decomposition is strong, both theoretically and numerically. Finally, a symmetry-induced model is proposed which may reduce a large number of bilinear terms in some special cases. Motivated by the virtual machine assignment problem, we also investigate a couple of general methods on the approximation of convex and concave envelopes for bilinear optimization over a hypercube. We establish several theoretical connections between different techniques and prove the equivalence of two seeming different relaxed formulations. An interesting research direction is also discussed. To address issues of uncertainty, a novel paradigm on general linear problems with uncertain parameters are proposed. This paradigm, termed as multipolar robust optimization, generalizes notions of static robustness, affinely adjustable robustness, fully adjustable robustness and fills the gaps in-between. As consequences of this new paradigms, several known results are implied. Further, we prove that the multipolar approach can generate a sequence of upper bounds and a sequence of lower bounds at the same time and both sequences converge to the robust value of fully adjustable robust counterpart under some mild assumptions
32
Ngueveu, Sandra Ulrich. "Problèmes de tournées de véhicules avec contraintes particulières pour la maîtrise des risques." Troyes, 2009. http://www.theses.fr/2009TROY0013.
Full textAbstract:
Cette thèse porte sur la résolution de deux problèmes de transport qui intègrent des contraintes ou des objectifs de maîtrise des risques : le problème de tournées de véhicules m-péripatétiques (m-PTVP) et le problème de tournées de véhicules cumulatives avec contraintes de capacité (PTVCC). Les applications ciblées sont du domaine de la logistique sécurisée, tel le transport de fonds, et de la logistique humanitaire, tel le transport de 1ers secours. Le m-PTVP a fait l'objet de la majeure partie de nos travaux. Il consiste à définir des tournées de véhicules de coût total minimal et sans arêtes communes sur m périodes telles que chaque client soit visité exactement une fois par période. Nous proposons différents modèles mathématiques, des bornes inférieures polynomiales, deux méta-heuristiques dont un algorithme de recherche taboue guidée avec la solution d'un b-couplage parfait, une approche de type génération de colonnes qui combine des heuristiques duales avec la génération de q- tournées, et enfin deux algorithmes de branchements et coupes. Le PTVCC identifie les tournées de véhicules qui minimisent la somme des dates d'arrivées chez les clients tout en respectant les contraintes de capacité des véhicules. Nous proposons un algorithme mémétique (MA) dont l'efficacité repose sur le découpage optimal de chromosomes en solutions et l'utilisation de pré-calculs déduits des propriétés du PTVCC que nous avons identifiées, lesquelles produisent également des formules de calcul de bornes inférieures. Notre MA est à ce jour la meilleure méta-heuristique publiée pour le cas particulier du problème du réparateur itinérant (= PTVCC mono-véhicule = TRP)This research concerns solving two transportation problems that integrate constraints or objective-fonctions related to the risk management: the m-Peripatetic Vehicle Routing Problem (m-PVRP) and the Cumulative Capacitated Vehicle Routing Problem (CCVRP). Applications can be found in the security logistics field, such as money transportation, and the humanitarian logistics field, such as vital goods supply after a natural disaster. Most of our work is about the m-PVRP. It consists in finding a set of routes of minimal total cost over m periods such that each customer is served once per period and two customers are never sequenced consecutively during two different periods. Different mathematical models are presented and the problem complexity is discussed. Then, we propose polynomial lower bounds, two metaheuristics including a tabu search with diversification and guided by a b-matching solution, a column-generation-like approach combining dual heuristics with q-routes generation, and finally two branch-and-cut algorithms. The CCVRP consists in minimizing the sum of arrival times at customers, instead of the classical route cost or length, subject to the vehicle capacity. We propose a memetic algorithm (MA). Its efficiency lies upon the optimal splitting procedure of chromosomes without trip delimiters into feasible routes to obtain a feasible solution. Pre-computations to speed up MA and valid formulas to compute lower bounds are deduced from some CCVRP properties we identified. Up to now, this MA is the best metaheuristic published on the special case of the Traveling Repairman Problem ( = single-vehicle PTVCC = TRP
33
Mohite, Shivaraj. "Observer Design for Nonlinear Systems using LMI Relaxation Techniques." Electronic Thesis or Diss., Université de Lorraine, 2023. http://www.theses.fr/2023LORR0326.
Full textAbstract:
Au cours des trois dernières décennies, la conception d'observateurs pour les systèmes dynamiques est devenue un sujet important dans le domaine des systèmes de contrôle. Ceci est dû au fait qu'un observateur est utilisé en temps-réel pour la supervision des systèmes, le contrôle des systèmes, ainsi que pour la prise de décision. Les observateurs d'état basés sur les techniques LMIs ont suscité une attention par rapport aux autres techniques d'observation. Cette thèse de doctorat porte sur les techniques de relaxation LMIs pour des classes de systèmes non linéaires avec des non-linéarités lipschitziennes. La contribution principale de la thèse est la proposition de nouvelles matrices dites « Matrix-Multiplier ». Les conditions LMIs obtenues en utilisant ces matrices (ainsi qu'une reformulation de la propriété de Lipschitz et la relation de Young de façon judicieuse) ont été testées moins contraignantes que les autres techniques existantes dans la littérature. Une extension au cas H_∞ a été proposée pour les systèmes en présence de bruits ou perturbations. Grace aux variables de décisions supplémentaires créées par les « Matrix-Multiplier » permettent d'améliorer la faisabilité des conditions LMIs. L'efficacité et la supériorité de la nouvelle technique ont été validées à travers plusieurs exemples illustratifs. Une version de la nouvelle approche LMI proposée est étendue à une classe de systèmes non linéaires avec des non-linéarités localement lipschitziennes, en présence des bruits/perturbations. Cela est réalisé en utilisant la structure d'observateur basée sur la projection de Hilbert. La nouvelle condition LMI est établie pour garantir le comportement ISS de l'erreur d'estimation d'état des observateurs proposés. De plus, l'approche LMI basée sur les multiplicateurs de matrices proposée est exploitée pour la stabilisation des systèmes non linéaires affectés par des perturbations en utilisant une commande basée observateurs. La mise en œuvre judicieuse des LMI basés sur les multiplicateurs de matrices a permis d'obtenir des conditions LMI moins conservatrices que les méthodes LMI existantes dans la littérature. Enfin, tous ces observateurs basés sur les LMI développés sont utilisés dans le domaine des véhicules autonomes pour diverses tâches, telles que l'estimation de l'état longitudinal, l'estimation de l'angle de glissement, etc., afin de valider leurs performancesOver the last three decades, observer design for dynamical systems has emerged as a pivotal topic in the control system domain. This is a consequence of the fact that observers are used to collect real-time information about the systems, monitor the systems, control the system, and make decisions. The LMI-based observers have garnered considerable attention among the various established observer methodologies. The thesis predominantly deals with the design of the LMI-based observers for the Lipschitz nonlinear systems. One of the valuable contributions of this thesis is the establishment of more generalized matrix-multiplier-based LMIs. These LMI conditions are derived through the utilization of reformulated Lipschitz property, Young inequalities, and newly defined matrix multipliers. Further, an LMI-based H_∞ observer is designed to estimate the states of the nonlinear systems under the presence of disturbances/noise by using the previously defined matrix multipliers. The proposed LMIs contain additional numbers of decision variables as compared to the existing approaches, which add extra degrees of freedom thus improving their feasibility. The effectiveness of the developed approach is validated through numerical examples. This new matrix-multiplier-based LMI approach is extended for the state estimation for a class of non-globally Lipschitz nonlinear systems under the effect of noise/disturbances. It is achieved by deploying the Hilbert projection-based observer structure. The novel LMI condition is established to ensure the ISS behaviour of the state estimation error of the proposed observers. Furthermore, the proposed matrix-multiplier-based LMI approach is exploited for the stabilization of the disturbance-affected nonlinear systems using the observer-based controller. The judicious implementation of the matrix-multiplier-based LMIs made it possible to obtain less conservative LMI conditions than existing LMI methods in the literature. Finally, all these developed LMI-based observers are used in the autonomous vehicle area for various tasks, such as longitudinal state estimation, slip angle estimation, and so on to validate their performances
34
Garaix, Thierry. "Etude et résolution exacte de problèmes de transport à la demande avec qualité de service." Avignon, 2007. http://tel.archives-ouvertes.fr/docs/00/53/48/94/PDF/thesegaraix.pdf.
Full textAbstract:
Nous étudions dans cette thèse un problème de construction de tournées de véhicules pour le transport de personnes à la demande (TAD) qui, combinant la souplesse des taxis à la capacité de regroupement des transports en commun, est une voie pour repenser nos pratiques en terme de mobilité. Après avoir défini puis classé plusieurs critères de qualité de service, nous en sélectionnons trois pour leur repésentativité : la minimisation de la distance totale parcourue, la maximisation du taux de remplissage des véhicules et la minimisation du temps perdu en transport. La méthode d'optimisation utilisée est basée sur une approche par décomposition appelée génération de colonnes. Nous nous plaçons dans le cas statique où toutes les demandes sont connues par avance. L'adaptation de cette méthode exacte aux trois critères choisis induit des développements originaux, comme la modélisation du réseau par un p-graphe ou l'optimisation d'une fonction objectif fractionnaire. Cette étude est intégrée à un projet pluridisciplinaire piloté par des géographes qui a pour sujet d'expérimentation la mise en place d'un TAD opérationnel dans le Pays du Doubs central (France). Un algorithme de résolution heuristique spécifique a été développé pour cette application. L'intégration des résultats des deux algorithmes à un Système d'Information Géographique permet une analyse des critères de qualité de service et de leurs interactions avec le teritoire d'un point de vue géomatique. Il en découle une étude sur la forme des tournées et plus particulièrement sur différentes mesures de leur sinuositéIn this thesis, we address routing problems deriving from on-demand transport systems (ODT). Such systems, combining taxi flexibility with public transport system advantages (grouping, price) seem well suited to the new mobility needs. We define and classify a large set of quality of service criteria. We select three of them among the most representative : the total distance travelled, the vehicle occupancy rate and the passenger wasted-time. We propose branch-and-price solution schemes for the three cases, under the assumption that demands are known in advance. The original quality of service objectives introduce non-standard features into the vehicle routing model, namely a multigraph and a fractional objective function, therefore inducing non-standard algorithms. This work is part of a multidisciplinary project managed by geographers. The implementation of an operational ODT in the Doubs Central area (France) is used as a testing ground for experimentations. For the practical use of this system, we propose an insertion heuristic in addition to the branch-and-price algorithm. A geomatic analysis of the interactions between quality of service criteria and the geographical area is carried out with a Geographic Information System, with a special focus on route shapes and route sinuosity measures
35
Mancel, Catherine. "Modélisation et résolution de problèmes d'optimisation combinatoire issus d'applications spatiales." Toulouse, INSA, 2004. http://www.theses.fr/2004ISAT0011.
Full textAbstract:
Nos travaux portent sur la modélisation et la résolution de problèmes d'optimisation combinatoire émergeant dans le cadre de la planification de missions spatiales. Ces problèmes de grande taille présentent des caractéristiques communes en termes de types de données, de contraintes et de critères à optimiser. Nous nous focalisons sur l'apport de la programmation linéaire pour ces problèmes, associée à des méthodes de simplification de l'espace de recherche, par décomposition ou grâce à des techniques de propagation de contraintes. Nous avons plus particulièrement étudié deux problèmes. Le premier concerne la planification de communications sonde/satellite et d'expériences dans un projet d'exploration martienne. Une décomposition de ce problème permet de le formuler comme deux problèmes indépendants : un problème de planification des communications que nous modélisons par un programme linéaire en nombres entiers et que nous résolvons de façon exacte par un algorithme classique, et un problème d'aide à la décision pour la planification des expériences, pour lequel nous établissons des courbes d'évaluation de la charge des ressources, déduites de l'application de techniques de propagation de contraintes basées sur un raisonnement énergétique. Le second problème étudié est celui de la planifiacation de prises de vue d'un satellite d'observation de la Terre. Nous proposons un modèle linéaire en variables mixtes et nous développons une approche de résolution par génération de colonnes, qui est une adaptation de la programmation linéaire au traitement de problèmes de grande taille, faisant appel à certaines techniques de décomposition des modèlesIn this work we are concerned with combinatorial optimization problems stemming from space missions planning. These huge problems have some common features concerning the type of data, constraints and criteria to be optimized. We focus on linear programming for modeling and solving these problems, associated to methods for search space simplification, using decomposition or some constraint propagation techniques. We more particularly address two problems. The first one concerns a mission which aims at a scientific investigation of Mars. It consists in planning both communication slots between martian probes and a satellite, and experiments on probes. We use linear integer programming to model and solve to optimality the sub-problem of communication slots planning, and we develop an decision-aid oriented method using constraint propagation for experiments planning. The second problem occurs in the context of the french program of Earth observing with satellites. It consists in selecting and scheduling images taken by one satellite in order to maximize a quality criterion. We give a linear model and we propose a column generation approach, based on the Dantzig-Wolfe decomposition of the model, to calculate upper bounds for this problem and in order to solve it
36
Blondel, Oriane. "Dynamiques de particules sur réseaux avec contraintes cinétiques." Paris 7, 2013. http://www.theses.fr/2013PA077156.
Full textAbstract:
Dans cette thèse, je m'intéresse à des modèles stochastiques de particules sur réseaux qui suivent une dynamique de Glauber avec contraintes cinétiques (KCSM), et particulièrement aux modèle Est et FA-1f. Ces modèles sont apparus en physique pour l'étude des systèmes vitreux. Dans ce document se trouve d'abord un résumé en français de son contenu. Puis viennent trois chapitres présentant le cadre dans lequel mes travaux s'inscrivent et montrant à la fois leurs contributions et à quelles notions et techniques ils font appel. Je centre ma présentation des KCSM sur les objets et résultats qui ont joué un rôle direct dans mes recherches. Mes articles sont regroupés en annexe avec éventuellement quelques extensions retranchées pour lE publication. Le premier chapitre est une introduction aux KCSM. Le deuxième chapitre présente des résultats hors équilibre pour les KCSM. J'expose d'abord des résultats de relaxation locale ; pour le modèle FA-1f il s'agit d'un travail commun avec N. Cancrini, F. Martinelli, C. Roberto et C. Toninelli. J'étudie ensuite la progression d'un front dans le modèle Est, et montre un théorème de forme ainsi qu'un résultat d'ergodicité pour le processus vu du front. Ce résultat repose sur la quantication de la relaxation locale du processus vu du front plutôt que sur des arguments classiques de sous-additivité. Le dernier chapitre explore des questions liées à la dynamique des KCSM à basse température (soit à haute densité). Je rappelle des résultats asymptotiques sur le trou spectral des modèles Estet FA-1f et propose quelques heuristiques et conjectures. Je m'intéresse ensuite au comportement à basse température du coecient de diusion d'un traceur dans un KCSM, dans l'optique de donner des réponses rigoureuses à des questions posées dans la littérature physiqueThis thesis is about stochastic lattice models of particle systems with Glauber dynamics and /kinetic constraints (KCSM), more specically the East and FA-1f models. These models were introduced in physics for the study of glassy systems. In this document one nds rst a summary of its contents (in French), then three introductory chapters in which I present the context of my works and show both what what my contributions add to the picture and on which notions and techniques they rely. In my presentation of KCSM, I focus on objects and results that are directly related to my research. Finally my papers are assembled in the Appendix, in some cases with extensions that were cut o for publication. The rst chapter is an introduction to KCSM. The second chapter presents non-equilibrium issues for KCSM. First I give results about out-of-equilibrium local relaxation; in the FA-1f mode it is a joint work with N. Cancrini, F. Martinelli, C. Roberto and C. Toninelli. Then I study the progression of a front in the East model and show a shape theorem as well as an ergodicity result for the process seen from the front. This result relies on quantifying the local relaxation of the process seen from the front rather than using classic sub-additivity arguments. The last chapter explores low-temperature (or high density) dynamics of KCSM. I rst recali asymptotic results about East and FA-1f spectral gaps and oer some heuristics and conjectures. I then focus on the low temperature behaviour of the diusion coecient of a tracer in a KCSM, so as to give rigorous answers to questions raised in the physics literature
37
Migot, Tangi. "Contributions aux méthodes numériques pour les problèmes de complémentarité et problèmes d'optimisation sous contraintes de complémentarité." Thesis, Rennes, INSA, 2017. http://www.theses.fr/2017ISAR0026/document.
Full textAbstract:
Dans cette thèse, nous avons étudié les méthodes de régularisation pour la résolution numérique de problèmes avec équilibres. Dans une première partie, nous nous sommes intéressés aux problèmes de complémentarité au travers de deux applications : les équations en valeur absolue et les problèmes de parcimonie. Dans une seconde partie, nous avons étudié les problèmes d'optimisation sous contraintes de .complémentarité. Après avoir définies des conditions d'optimalité pour ces problèmes nous avons proposé une nouvelle méthode de régularisation appelée méthode des papillons. A partir d'une étude de la résolution des sous-problèmes de la régularisation nous avons défini un algorithme avec des propriétés de convergence forte. Tout au long de ce manuscrit nous nous sommes concentrés sur les propriétés théoriques des algorithmes ainsi que sur leurs applications numériques. La dernière partie de ce document est consacrée aux résultats numériques des méthodes de régularisationIn this thesis, we studied the regularization methods for the numerical resolution of problems with equilibria. In the first part, we focused on the complementarity problems through two applications that are the absolute value equation and the sparse optimization problem. In the second part, we concentrated on optimization problems with complementarity constraints. After studying the optimality conditions of this problem, we proposed a new regularization method, so-called butterfly relaxation. Then, based on an analysis of the regularized sub-problems we defined an algorithm with strong convergence property. Throughout the manuscript, we concentrated on the theoretical properties of the algorithms as well as their numerical applications. In the last part of this document, we presented numerical results using the regularization methods for the mathematical programs with complementarity constraints
38
Tran, Minh Binh. "La méthode de décomposition de domaines de Schwarz pour les problèmes linéaires et non-linéaires." Paris 13, 2011. http://www.theses.fr/2011PA132018.
Full textAbstract:
Les méthodes de décomposition de domaines sont des procédures pour paralléliser et résoudre les équations aux dérivées partielles numériquement : à chaque itération on résout les équations originales sur les sous-domaines. Avec le développement des méthodes de décomposition de domaines, une théorie de convergence est nécessaire et beaucoup d’effort a été fait dans cette direction de recherche; cependant le problème est encore ouvert, même pour les méthodes classiques. Dans la première partie de cette thèse, on propose une nouvelle méthode pour résoudre le problème de convergence des algorithmes de Schwarz. Notre méthode s’applique aux équations elliptiques et paraboliques linéaires et non linéaires. Elle est considérée quand les solutions sont aux sens fort et faible, et même quand il y a une explosion des solutions en temps fini. Dans la deuxième partie, nous appliquons notre théorie de convergence aux équations primitives de l’océan et aux équations différentielles stochastiques, où un nouveau schéma de décomposition de domaines à quatre étapes est introduit, basé sur le schéma de quatre étapes pour les équations de différentielles stochastiques du type forward-backward de Ma, Protter et Yong. Les méthodes de Schwarz optimisées forment une nouvelle classe de méthodes de Schwarz qui permettent aux algorithmes de converger plus vite dans tous les cas avec ou sans recouvrement grâce à l’amélioration des conditions de transmission. Dans la troisième partie de cette thèse, nous étudions ici cette classe d’algorithmes avec les conditions de transmission de Robin et d’ordre deux pour l’équation de la chaleur en dimensions 1 et 2The Schwarz domain decomposition methods are procedures to parallelize and solve partial differential equations numerically, in which each iteration involves the solutions of the original equations on smaller subdomains. Together with the development of domain decomposition methods, a theory of convergence for the methods is really needed and many efforts have been made in this direction; however, the problem still remains open, even for classical methods. In the first part of the thesis, we introduce a new method to solve the convergence problem of Schwarz methods. Our method works for parabolic and elliptic equations, linear and non-linear. In the second part, we apply our method to study the primitive equations and the forward-backward stochastic differential equations, where a new four-step domain decomposition scheme is introduced, based on the four-step scheme of Ma, Protter and Young. Optimized Schwar methods is a new class of Schwarz methods, which converges much faster than the classical ones, thanks to the improvement of the transmission conditions. In the third part of this thesis, we study this class of algorithms with Robin and second order transmission conditions for heat equation in 1 and 2 dimensions
39
Chabrier, Alain. "Génération de colonnes et de coupes utilisant des sous-problèmes de plus court chemin." Angers, 2003. http://www.theses.fr/2003ANGE0029.
Full textAbstract:
Les méthodes de génération de colonnes ont depuis quelques années fait l'objet de nombreuses publications concernant la résolution d'un nombre croissant de problèmes d'optimisation combinatoire. Elles reposent sur une uti-lisation particulière de la méthode du simplexe sur un problème décomposé et restreint. Un problème auxiliaire permet de générer les variables non prises en compte initialement. Dans cette thèse nous nous intéressons aux cas où le problème auxiliaire est un problème de plus court chemin dans un graphe. Di-verses améliorations ont été proposées dans la littérature, mais elles se limitent souvent à des instances particulières de la classe de problèmes traités. Cette thèse vise à faciliter la réutilisation d'améliorations entre différents problèmes. Pour cela, nous présentons d'abord un formalisme générique per-mettant de modéliser les problèmes ainsi qu'une description de la recherche de solutions utilisant des goals. Nous présentons ensuite plusieurs améliorations pratiques applicables à di-vers problèmes. Plus concrètement, les contributions comportent : - un algorithme efficace de plus court chemin élémentaire dans le sous--problème, - une combinaison d'heuristiques d'expert et de programmation par con-traintes pour le sous-problème, - des stratégies de recherche pour le sous-problème, - une contrainte globale de plus court chemin en programmation par con-traintes pour le sous-problème, - l'introduction de coupes dans le problème maître décomposé, - des heuristiques et stratégies de recherche dans le problème maître. Ces améliorations sont enfin validées par la résolution de trois applications réelles de natures très différentes : la tournée de véhicules, la planification de ressource et la conception de réseau. Pour chacune des applications, nous donnons des résultats expérimentaux montrant l'apport de l'une ou plusieurs de ces améliorations sur la qualité des résultats obtenus. Un environnement de génération de colonnes et de coupes a également été développé permettant de mettre en oeuvre facilement l'ensemble de ces idéesIn recent years, column generation methods have been the subject of many publications about solving a greater number of combinatorial optimisation pro-blems. They correspond to a particular use of the revised Simplex method on a decomposed and restricted problem. An auxiliary problem generates new va-riables not present initially. In this thesis, we focus our interest on the cases where the auxiliary problcm is a constrained shortest path problem in a graph. Various improvcments have been proposed in thc literature, but they arc all limitcd to a particular problem. This thesis proposes to facilitate thc reuse of those improvcments in different problems. For this, we propose a generic formalism to model such problems and a description of thc scarch for solutions using goals. We then present new and different practical improvements applicable te varions problems. More precisely, the contributions are : an efficient algorithm for elcmentary shortcst path in the subproblem, a combination of expert heuristics and Constraint Programming in the subproblem, search strategies for the subproblem, a Constraint Programming global constraint for shortest path subproblem, cutting planes applied to the path-based master problem, heuristics and search strategies for the master problem. Those improvements are validated on three different real applications : ve-hicle routing, crew scheduling, and network design. For each of those applications, we produce several experimental results sho-wing how some combinations of the proposed contributions help to improve the ultimate solutions. Finally, a column and cut generation framework has been implemented that eases the development of such applications and that includes most of our pro-posal
40
Dongmo, Nguepi Guissel Lagnol. "Modèles mathématiques et numériques avancés pour la simulation du polymère dans les réservoirs pétroliers." Electronic Thesis or Diss., université Paris-Saclay, 2021. http://www.theses.fr/2021UPASG077.
Full textAbstract:
Une technique efficace pour accroître la production d’un champ pétrolier consiste à y injecter un mélange d’eau et de polymère. La viscosité du polymère réduit en effet la mobilité de l’eau, qui pousse alors mieux l’huile, d’où un taux d’extraction plus élevé. La simulation numérique d’un tel procédé de récupération d’hydrocarbures revêt donc d’une importance capitale. Or, malgré des décennies de recherche, la modélisation des écoulements avec polymère en milieu poreux et sa résolution numérique demeurent un sujet difficile. D’une part, les modèles habituellement employés par les ingénieurs de réservoir présentent, au mieux, des singularités de type résonance qui les rend faiblement hyperboliques. Ce défaut donne lieu à certaines complicationsD’une part, les modèles habituellement employés par les ingénieurs de réservoir présentent, au mieux, des singularités de type résonance qui les rend faiblement hyperboliques. Ce défaut donne lieu à certaines complications mais reste acceptable. Au pire, quand on veut incorporer l’effet du volume de pore inaccessible (IPV), les modèles deviennent non hyperboliques, ce qui aggrave les instabilités numériques susceptibles d’apparaître.D’autre part, les schémas numériques classiques ne conduisent pas à des résultats satisfaisants. Sans IPV, la diffusion excessive autour de l’onde de contact fait perdre les informations pertinentes. Avec IPV, l’existence des valeurs propres complexes crée des instabilités exponentielles au niveau continu qu’il faut traiter au niveau discret sous peine d’arrêt prématuré du code.L’objectif de cette thèse est de remédier à ces difficultés. Au niveau des modèles, nous analysons plusieurs lois d’IPV et établissons une équivalence entre deux d’entre elles. Nous proposons de surcroît des conditions suffisantes raisonnables sur la loi d’IPV en vue de l’hyperbolicité faible du système d’écoulement. Au niveau des schémas pour le problème sans IPV, nous préconisons une correction afin d’améliorer la précision des discontinuités de contact. Pour le problème avec IPV,nous élaborons une méthode de relaxation qui garantit la stabilité des calculs quelle que soit la loi IPVAn effective technique to increase production in an oil field is to inject a mixture of water and polymer. The viscosity of polymer reduces the mobility of water, which then pushes oil better, resulting in a higher extraction rate. The numerical simulation of such an enhanced oil recovery is therefore of paramount importance. However, despite decades of research, the modeling of polymer flows in porous media and its numerical resolution remains a difficult subject.On the one hand, the models traditionally used by reservoir engineers exhibit, in the best case, resonance-like singularities that make them weakly hyperbolic. Thisdefect gives rise to some complications but remains acceptable. In the worst case, when we wish to incorporate the effect of the inaccessible pore volume (IPV), themodels become non-hyperbolic, which exacerbates the numerical instabilities that are likely to appear.On the other hand, classical numerical schemes do not yield satisfactory results. Without IPV, the excessive diffusion around the contact wave causes the most relevant information to be lost. With IPV, the existence of complex eigenvalues generates exponential instabilities at the continuous level that must be addressed at the discrete level to avoid a premature stop of the code.The objective of this thesis is to remedy these difficulties. Regarding models, we analyze several IPV laws and show an equivalence between two of them. Furthermore, we propose reasonable sufficient conditions on the IPV law to enforce weak hyperbolicity of the flow system. Regarding schemes for the problem without IPV, we advocate a correction to improve the accuracy of contact discontinuities. For the problem with IPV, we design a relaxation method that guarantees the stability of the calculations for all IPV laws
41
Haddaoui, Khalil. "Méthodes numériques de haute précision et calcul scientifique pour le couplage de modèles hyperboliques." Thesis, Paris 6, 2016. http://www.theses.fr/2016PA066176/document.
Full textAbstract:
La simulation numérique adaptative d'écoulements présentant des phénomènes multi-échelles s'effectue généralement au moyen d'une hiérarchie de modèles différents selon l'échelle mise en jeu et le niveau de précision requis. Ce type de modélisation numérique entraîne des problèmes de couplage multi-échelles complexes. Cette thèse est ainsi dédiée au développement, à l'analyse et à la mise en œuvre de méthodes performantes permettant de résoudre des problèmes de couplage en espace de modèles décrits par des systèmes d'équations aux dérivées partielles hyperboliques.Dans une première partie, nous développons et analysons une méthode numérique dédiée au couplage interfacial des équations d'Euler mono-dimensionnelles. Chacun des systèmes de lois de conservation est muni d'une loi de pression distincte et l'interface de couplage séparant ces modèles est supposée fixe et infiniment mince. Les conditions de transmission sont modélisées par un terme source mesure localisé à l'interface de couplage. Le poids associé à cette mesure modélise les pertes de conservation à l'interface (typiquement des pertes de charge) et sa définition permet l'application de plusieurs stratégies de couplage. Notre méthode d'approximation repose sur les techniques d'approximation par relaxation de type Suliciu. La résolution exacte du problème de Riemann pour le système relaxé nous permet de définir un schéma numérique équilibre pour le modèle de couplage. Ce schéma préserve certaines solutions stationnaires du modèle de couplage et est applicable pour des lois de pression générales. L'implémentation de notre méthode permet de mener des expériences numériques illustrant les propriétés de notre schéma. Par exemple, nous montrons qu'il est possible de contrôler l'écoulement à l'interface de couplage en calculant des poids solutions de problèmes d'optimisation sous contraintes.La deuxième partie de cette thèse est dédiée au développement de deux schémas numériques d'ordre arbitrairement élevé en espace pour l'approximation des solutions stationnaires du problème mixte associé au modèle de Jin et Xin. Nos schémas d'approximation reposent sur la méthode de Galerkin discontinue. L’approximation des solutions du problème mixte par notre premier schéma fait intervenir uniquement des erreurs de discrétisation tandis que notre deuxième schéma est constitué à la fois d'erreurs de modélisation et de discrétisation. L'erreur de modélisation provient du remplacement, dans certaines régions spatiales, de la résolution du modèle de relaxation par celle de l'équation scalaire équilibre associée. Sous l'hypothèse d'une interface de couplage éventuellement caractéristique, la résolution du problème de Riemann associé au modèle couplé nous permet de construire un schéma numérique d'ordre arbitrairement élevé prenant en compte l'éventuelle existence de couches limites à l'interface de couplage. Enfin, la mise en œuvre de ces méthodes nous permet d'analyser quantitativement et qualitativement les erreurs de modélisation et de discrétisation commises lors de l'utilisation du schéma couplé. Ces erreurs sont fonction du niveau de raffinement de maillage utilisé, du degré de polynôme choisi et de la position de l'interface de couplageThe adaptive numerical simulation of multiscale flows is generally carried out by means of a hierarchy of different models according to the specific scale into play and the level of precision required. This kind of numerical modeling involves complex multiscale coupling problems. This thesis is thus devoted to the development, analysis and implementation of efficient methods for solving coupling problems involving hyperbolic models.In a first part, we develop and analyze a coupling algorithm for one-dimensional Euler systems. Each system of conservation laws is closed with a different pressure law and the coupling interface separating these models is assumed fix and thin. The transmission conditions linking the systems are modelled thanks to a measure source term concentrated at the coupling interface. The weight associated to this measure models the losses of conservation and its definition allows the application of several coupling strategies. Our method is based on Suliciu's relaxation approach. The exact resolution of the Riemann problem associated to the relaxed system allows us to design an extremely accurate scheme for the coupling model. This scheme preserves equilibrium solutions of the coupled problem and can be used for general pressure laws. Several numerical experiments assess the performances of our scheme. For instance, we show that it is possible to control the flow at the coupling interface when solving constrained optimization problems for the weights.In the second part of this manuscript we design two high order numerical schemes based on the discontinuous Galerkin method for the approximation of the initial-boundary value problem associated to Jin and Xin's model. Our first scheme involves only discretization errors whereas the second approximation involves both modeling and discretization errors. Indeed in the second approximation, we replace in some regions the resolution of the relaxation model by the resolution of its associated scalar equilibrium equation. Under the assumption of a possible characteristic coupling interface, we exactly solve the Riemann problem associated to the coupled model. This resolution allows us to design a high order numerical scheme which captures the possible boundary layers at the coupling interface. Finally, the implementation of our methods enables us to analyze quantitatively and qualitatively the modeling and discretization errors involved in the coupled scheme. These errors are functions of the mesh size, the degree of the polynomial approximation and the position of the coupling interface
42
Rodriguez, Garcia Javier. "Numerical study of dynamic relaxation methods and contribution to the modelling of inflatable lifejackets." Lorient, 2011. http://www.theses.fr/2011LORIS247.
Full textAbstract:
Dynamic relaxation (DR) is a numerical method introduced in 1965 by A. S. Day in the book "The Engineer". From 1983, with the works presented by P. Underwood, it became more and more used. Since then, many applications were found, and several authors presented different improvements on the method in order to optimize the calculations. Nowadays, its use is widely spread in fields as structural dynamics (particularly in form-finding), geomechanics or biomechanics. When using DR in numerical simulations, researchers followed two different paths in the choice of a damping strategy for the oscillations: some used DR combined with a viscous damping and others used DR combined with kinetic damping. However, it is difficult to find comparisons between both methods to help deciding whether one is better than the other for a particular application. Focused in the field of form-finding of thin structures, the main objective of this thesis is to make a contribution to the development of DR methods and a review of the existing DR methods in order to compare them. Therefore, a scientific paper is presented in this thesis comparing different DR methods with both kinetic and viscous damping in the case of form-finding of inflatable structures. Also, another paper is detailed where an extension for the DR method with kinetic damping is proposed. Then, as an application for the studied DR methods, a contribution to the modelling of inflatable lifejackets will be presented. The aim of this part of the work is to present some contributions to the creation of a numerical tool permitting to test the functioning of an inflatable lifejacket by means of Finite Elements calculations. This work covers the creation of a parameterized mannequin, a rough characterization of the involved technic textile, improvements in the numerical simulation of the inflation of the lifejacket using the DR method, and also a fist approach to the water dynamics and contact mechanics that will be involved in the final simulationLa Relaxation Dynamique (RD) est une méthode numérique présentée en 1965 par A. S. Day dans l'ouvrage "The Engineer". Depuis 1983, avec les travaux présentés par P. Underwood, la méthode est de plus en plus utilisée. Depuis ces travaux fondateurs, la méthode de RD a trouvé de nombreuses applications, et plusieurs auteurs ont introduit différentes améliorations de la méthode en cherchant l'optimisation des calculs. Désormais, son utilisation s'est largement étendue aux domaines tels que la dynamique des structures (particulièrement la recherche de forme), la geomécanique ou la biomécanique. Dans le cadre de l'utilisation de la RD les chercheurs ont suivi deux chemins différents pour le choix d'une stratégie d'amortissement des oscillations: certains ont utilisé la RD combinée avec un amortissement visqueux et d'autres ont utilisé la RD combinée avec un amortissement cinétique. Néanmoins, très peu de comparaisons entre ces deux méthodes ont été exposées ayant par but d'aider à choisir l'une ou l'autre pour une application en particulier. Focalisés dans la recherche de forme de structures minces, le principal objectif de cette thèse est d'apporter une contribution au développement des méthodes de RD parallèlement à une revue des méthodes existantes en vue de les comparer. Un premier article scientifique est ainsi détaillé dans ce travail en comparant les différentes méthodes de RD avec les deux types d'amortissement, cinétique et visqueux, pour le cas particulier de la recherche de forme de structures gonflables. Puis un second papier est décrit, où une extension pour la méthode de RD avec amortissement cinétique est proposée. En tant qu'application des méthodes de RD étudiées, une contribution à la modélisation des gilets de sauvetage gonflables est exposée. Le but de cette partie de la thèse est d'introduire quelques contributions à la création d'un outil numérique permettant de tester le fonctionnement d'un gilet de sauvetage gonflable en situation en utilisant la méthode des Eléments Finis. Ce travail comprend la création d'un mannequin paramétré, une caractérisation grossière du textile technique impliqué, des améliorations concernant la simulation numérique du gonflage du gilet en utilisant la méthode de RD, et finalement une première approche à la dynamique de l'eau et la mécanique du contact qui seront présents dans la simulation globale
43
Benamar, Fayçal. "Transport terrestre multimodal de conteneurs maritimes : modèle de tournées simultanées des conteneurs et des véhicules." Châtenay-Malabry, Ecole centrale de Paris, 1995. http://www.theses.fr/1995ECAP0423.
Full textAbstract:
Cette thèse présente une formulation mathématique et un algorithme de programmation mathématique pour la résolution optimale d'un problème du transport terrestre de conteneurs maritimes: le problème de tournées simultanés et coordonnées des conteneurs et des véhicules dans un contexte multimodal. Nous nous intéressons tout particulièrement au problème opérationnel qui consiste à satisfaire à moindre cout un ensemble de demandes de mouvement de conteneurs charges et de conteneurs vides entre différentes paires origine/destination. Les demandes sont formulées soit par des clients, soit par la compagnie pour une meilleure répartition de ses conteneurs. Il s'agit, pour satisfaire cet objectif, de déterminer l'ensemble des cheminements des conteneurs pour toutes les paires origine/destination et simultanément, l'ensemble des mouvements des véhicules routiers devant assurer une partie des opérations physiques de transport des conteneurs dans un contexte multimodal. Nous présentons une approche de modélisation originale dans le cas déterministe. Le modèle mathématique propose présente la particularité de reposer sur deux types de variables de décision, reflétant la nécessaire prise en compte simultanée des mouvements des conteneurs et des véhicules. Nous présentons également l'approche de résolution que nous avons développée. Elle est basée sur des techniques de Branch & Price (qui combinent génération de colonnes et Branch & Bound) pour la résolution optimale du problème. Pour valider notre approche, nous avons développé une base de données et des problèmes test et une maquette informatique qui a permis l'obtention de résultats très encourageants
44
Gdoura, Mohamed Khaled. "Problème de Stokes avec des conditions aux limites non-linéaires : analyse numérique et algorithmes de résolution." Caen, 2011. http://www.theses.fr/2011CAEN2021.
Full textAbstract:
Ce travail est un premier pas dans l’analyse math´ematique des probl`emes li´es `a la simulation du remplissage du moule par un polym`ere fondu en tenant compte de l’´eventuel glissement sur les parois solides. Notre travail est focalis´e sur le probl`eme de Stokes avec des conditions aux limites de type Tresca vue que les r´esultats d’analyse num´erique de ce type de probl`emes sont tr`es rares. Dans la premi`ere partie on commence d’abord par ´ecrire le probl`eme primal sous forme d’une in´equation variationnelle. Le terme de frottement apparait sous forme d’une fonction non-diff´erentiable. On propose par la suite une formulation mixte `a trois champs dans laquelle on dualise le frottement et on impose div(u) = 0 `a l’aide du multiplicateur de Lagrange p s’identifiant `a la pression. L’existence et l’unicit´e de la solution de cette formulation est garantie par une condition inf-sup continue qu’on prouve. Les ´el´ements finis P1 bulle/P1 pour le champs (u, p) et P1 pour le multiplicateur d´efinit sur le bord de Tresca ont permis de discr´etiser le probl`eme r´esultant. On montre que des conditions inf-sup discr`etes découplées sur le pression p et la contrainte tangentielle sont suffisantes pour la stabilit´e du probl`eme discret. Des estimations d’erreurs optimales ont ´et´e d´eriv´ees. La deuxi`eme partie porte sur l’estimation de la valeur optimale des p´enalit´es des algorithmes utilis´es, connus respectivement dans la litt´erature sous le nom ALG2 et ALG3. L’´equivalence entre les m´ethodes de directions altern´ees et la formulation en lagrangien augment´e a permis de r´e´ecrire les algorithmes sous forme d’un probl`eme d’´evolution dual discr´etis´e en temps par un sch´ema de splitting classique mettant en jeu des op´erateurs multivoques maximaux monotones. On montre d’abord la convergence dans le cas continu des deux algorithmes vers la solution stationnaire du probl`eme d’´evolution. On d´eduit par la suite la valeur optimale de la p´enalit´e de chaque algorithme `a partir de l’estimation de sa vitesse de convergence. La derni`ere partie porte sur deux m´ethodes de d´ecomposition de domaine bas´ees sur les algorithmes d’Uzawa appliqu´es au probl`eme de d´epart. Des tests num´eriques ont ´et´e r´ealis´es et un pr´econditionneur a ´et´e proposé pour la deuxième approcheThis work is a first step in the analysis of mathematical problems arising from numerical simulation of mold filling process by polymer melt which can slip on solid wall. We focus on Stokes problem with Tresca boundary conditions since numerical analysis of such problem is rare. In the first part of the manuscript we begin by setting the primal problem written as a variational inequality. The friction term is presented by a nondifferential function. Then, we propose a three field mixed formulation in which friction is dualized and div(u) = 0 is forced by the Lagrange multiplier p identified to the pressure. Existence and uniqueness of the solution of such formulation is guaranteed by continuous inf-sup condition that we prove. P1 bubble-P1 finite element for (u, p) and P1 for , defined on the Tresca boundary, are used to discretize the resulting problem. We prove that only two uncoupled discrete inf-sup conditions on the pressure p and the shear stress are sufficient to ensure the stability of the discrete problem. Optimal error estimates are derived. The second part is devoted to the estimation of the optimal value of relaxation parameters in the used algorithms, known as ALG2 & ALG3. Using equivalence between alternating-direction methods and augmented Lagrangian formulation, we write ALG2 & ALG3 as a dual evolution problem discretized by some classical splitting scheme involving multivalued maximal monotone operators. We prove the convergence of the algorithms, in continuous case, to the steady state solution of the dual evolution problem and we deduce the optimal value of relaxation parameters after stimating the rate convergence of the two algorithms. In the last part, we present two domain decomposition methods based on Uzawa algorithms to solve Stokes problem with slip boundary conditions. Numerical tests are carried out and a preconditioner is proposedfor the second approache
45
Corro, Caio. "Lagrangian Based Approaches for Lexicalized Tree Adjoining Grammar Parsing." Thesis, Sorbonne Paris Cité, 2018. http://www.theses.fr/2018USPCD051.
Full textAbstract:
Ces dernières années, des méthodes issues de l'optimisation combinatoire ont été appliquées avec succès pour résoudre des problèmes algorithmiques difficiles en Traitement Automatique des Langues (TAL). Nous suivons cette méthodologie dans le cadre de l'analyse syntaxique avec des Grammaires d'Arbres Adjoints Lexicalisés; Plus précisément, un problème d'analyse est d'abord réduit à un problème de sélection de sous-graphe. Ensuite nous formulons ce dernier sous forme de Programme Linéaire en Nombres Entiers. Beaucoup d'algorithmes ont été proposés pour ces formulations. Nous nous concentrons sur la Relaxation Lagrangienne qui a reçu beaucoup d'attention de la part de la communauté du TAL. La particularité de notre méthode réside dans le fait que nos algorithmes résolvent des problèmes généraux et peuvent donc être testés sur différentes donnéesIn linguistics and Natural Language Processing (NLP), syntax is the studyof the structure of sentences in a given language. Two approaches have mainlybeen considered to describe them: dependency structures and phrase-structures.A dependency links a pair of words together with its relation type whereas aphrase-structure describe a sentence by means of a hierarchy of word sets calledconstituents. In this thesis, we focus on phrase-structure parsing, that is thecomputation of the constituency structure of a given sentence. Context-FreeGrammars (CFGs) have been widely adopted by the NLP community due totheir simplicity and the low complexity of their parsing algorithms. However,CFGs are too limited in order to describe all phenomena observed in naturallanguage structures. Therefore, Lexicalized Tree Adjoining Grammars (LTAGs)have been widely studied as a plausible alternative, among others. They aremore expressive than CFGs but can also be parsed in polynomial time. Unfortunately,the best known algorithm has a O(n7) time complexity with n thelength of the input sentence. Thus, in practice most algorithms are based ongreedy methods which require fairly strong independence assumptions. Themain approach in the literature, called supertagging, lters the search space ina pre-processing step while ignoring long distance relationships, one of the mainmotivation for LTAGs.In the past years, combinatorial optimization techniques have been successfullyapplied to computationally challenging NLP tasks. We follow this line ofwork in the case of LTAG parsing. More precisely, in our setting, a given NLPproblem is reduced to a subgraph selection problem. As such, it has a genericform which may interest other research communities. Then we formulate thegeneric graph problem as an Integer Linear Program. Integer Linear Programinghas been widely studied and many optimization methods exist. We focus onLagrangian relaxation which previously received much attention from the NLPcommunity. Interestingly, the proposed algorithms can be parametrized to Et arange of different data without impacting eciency.Our erst contribution is a novel pipeline for LTAG parsing. Contrary tothe supertagging approach, we propose a pre-processing step which takes intoaccount relationships between words: well-nested dependency parsing with 2-bounded block degree. An algorithm with a O(n7) time complexity has beenproposed for this problem in the literature, which is similar to the standardLTAG parser complexity. In order to tackle the complexity challenge, we showthat it can be reduced to a subgraph selection problem which can be expressed23via a generic ILP. With our algorithm, the well-nested constraint can easily betoggled o and the block degree bound can be changed. Thus, as an example,it can be used for parsing problems related to other lexicalized grammars. Weexperiment on several problems showing the emciency and usefulness of ourmethod.Our second contribution is a novel approach for discontinuous constituentparsing. We introduce a variant of LTAG for this task. Parsing is then equivalentto the joint tagging and non-projective dependency parsing problem. Weshow that it can be reduced to the Generalized Maximum Spanning Arborescenceproblem which has been previously studied in the combinatorial optimizationliterature. A novel resolution algorithm based on Lagrangian relaxation isproposed. We experiment on two standard discontinuous constituent datasetsand obtain state-of-the-art results alongside competitive decoding speed
46
Marques, Guillaume. "Problèmes de tournées de véhicules sur deux niveaux pour la logistique urbaine : approches basées sur les méthodes exactes de l'optimisation mathématique." Thesis, Bordeaux, 2020. http://www.theses.fr/2020BORD0199.
Full textAbstract:
Cette thèse s’intéresse principalement au développement de méthodes d’optimisation mathématique exactes pour résoudre des problèmes de tournées de véhicules dans un réseau de distribution à deux niveaux. Dans un tel réseau, des camions circulent au premier niveau et transportent des marchandises d’un centre de distribution vers des dépôts intermédiaires appelés « satellites ». Au second niveau, des véhicules légers récupèrent les marchandises aux satellites puis livrent les clients. Chaque client doit être visité une seule fois. L’objectif du problème de tournées de véhicules sur deux niveaux est de minimiser le coût total de transport dans un tel réseau de distribution.Le premier chapitre présente succinctement l’algorithme de « branch-and-cut-and-price » que nous utilisons tout au long de la thèse.Le second chapitre s’intéresse au « Two-Echelon Capacitated Vehicle Routing Prob- lem ». Nous présentons une nouvelle formulation du problème basée sur des routes qui ne contient pas de variable pour déterminer les quantités de marchandises livrées aux satellites. Nous proposons une nouvelle stratégie de branchement qui permet de significativement réduire la taille de l’arbre de branch-and-bound. Enfin et surtout, nous présentons une nouvelle famille d’inégalités valides nommée « satellite supply inequalities ». Nous montrons que cette nouvelle famille améliore la qualité de la borne duale au nœud racine de l’arbre de « branch-and-bound ». Les expérimentations montrent que notre algorithme résout toutes les instances de la littérature qui contiennent jusqu’à 200 clients et 10 satellites. C’est le double de la taille des instances qui étaient résolues à l’optimalité jusqu’ici.La troisième chapitre s’intéresse au « Two-Echelon Vehicle Routing Problem with Time Windows ». Ici, nous considérons une variante avec des contraintes de précédence aux satellites : un camion doit livrer les marchandises à un satellite avant qu’elles soient chargées dans un véhicule léger. C’est une relaxation de la variante avec synchronisation exacte considérée dans la littérature. Nous traitons les variantes « single trip » et « multi trip » du problème avec contraintes de précédence. Dans la seconde variante, les véhicules légers partent d’un dépôt, récupèrent les marchandises aux satellites, puis effectuent plusieurs tournées. Nous proposons une formulation basée sur les routes dont le nombre de contraintes de précédence croît exponentiellement en fonction du nombre de satellites. Un algorithme basé sur une coupe minimum est proposé pour séparer ces contraintes. Nous montrons aussi comment prendre en compte ces contraintes dans le problème de pricing de l’algorithme de génération de colonnes. Les expérimentations montrent que notre algorithme peut résoudre à l’optimalité des instances qui contiennent jusqu’à 100 clients. De plus, nous montrons que la variante du problème avec contraintes de précédence donne des résultats identiques à ceux de la variante avec synchronisation exacte pour les instances « single trip » de la littérature.La quatrième chapitre s’intéresse à des problèmes de tournées de véhicules contenant des contraintes de type sac-à-dos. Nous présentons des coupes de type « route load knapsack ». Ces coupes sont utilisées pour résoudre les trois problèmes suivants: « Capacitated Vehicle Routing Problem with Capacitated Multiple Depots », « Location- Routing Problem » et « Vehicle Routing Problem with Time Windows and Shifts ». Ces problèmes apparaissent lorsque les routes au premier niveau du réseau de distribution à deux niveaux sont fixées. Nos expérimentations permettent de trouver de nouvelles solutions optimalesThe main focus of this thesis is to develop mathematical optimization based exact methods to solve vehicle routing problems in two-level distribution systems. In such a system, the first level involves trucks that ships goods from a distribution center to intermediate depots called satellites. The second level involves city freighters that are loaded with goods at satellites and deliver the customers. Each customer must be visited once. The two-echelon vehicle routing problem seeks to minimize the total transportation cost in such a distribution system.The first chapter gives an overview of the branch-and-cut-and-price framework that we use throughout the thesis.The second chapter tackles the Two-Echelon Capacitated Vehicle Routing Problem. We introduce a new route based formulation for the problem which does not use variables to determine product flows in satellites. We propose a new branching strategy which significantly decreases the size of the branch-and-bound tree. Most importantly, we suggest a new family of satellite supply inequalities, and we empirically show that it improves the quality of the dual bound at the root node of the branch-and-bound tree. Experiments reveal that our algorithm can solve all literature instances with up to 200 customers and 10 satellites. Thus, we double the size of instances which can be solved to optimality.The third chapter tackles the Two-Echelon Vehicle Routing Problem with Time Windows. We consider the variant with precedence constraints at the satellites: products should be delivered by an urban truck to a satellite before loading them to a city freighter. This is a relaxation of the synchronisation variant usually considered in the literature. We consider single-trip and multi-trip variants of this problem. In the first one, city freighters start from satellites and do a single trip. In the second one, city freighters start from a depot, load product at satellites, and do several trips. We introduce a route based formulation that involves an exponential number of constraints to ensure precedence relations. A minimum-cut based algorithm is proposed to separate these constraints. We also show how these constraints can be taken into account in the pricing problem of the column generation approach. Experiments show that our algorithm can solve to optimality instances with up to 100 customers. The algorithm outperforms significantly another recent approach proposed the literature for the single-trip variant of the problem. Moreover, the “precedence relaxation” is exact for single-trip instances.The fourth chapter considers vehicle routing problems with knapsack-type constraints in the master problem. For these problems, we introduce new route load knapsack cuts and separation routines for them. We use these cuts to solve to optimality three problems: the Capacitated Vehicle Routing Problem with Capacitated Multiple Depots, the standard Location-Routing Problem, and the Vehicle Routing Problem with Time Windows and Shifts. These problems arise when routes at first level of the two-level distribution system are fixed. Our experiments reveal computational advantage of our algorithms over ones from the literature
47
Hussein, Manal. "Comportement asymptotique des solutions d'équations de type Schrödinger non linéaires faiblement amorties." Thesis, Lille 1, 2009. http://www.theses.fr/2009LIL10083/document.
Full textAbstract:
Cette thèse porte sur l'étude du comportement asymptotique de quelques équations dissipatives en présence d'un amortissement et une force extérieure. Notre travail se divise en quatre chapitres. Dans le premier chapitre, on considère un modèle réduit uni-dimensionnel d'un système de Davey-Stewartson, une équation aux dérivées partielles de type Schrödinger non linéaire avec une non linéarité non locale, avec un terme de force et un terme d'amortissement. On démontre l'existence d'un attracteur global régulier pour le système dynamique associé. Dans le deuxième chapitre, on travaille sur un système de Davey-Stewartson DS dans le cas elliptique-elliptique. On démontre l'existence et la régularité d'un attracteur global avec données initiales assez petites. Dans le troisième chapitre, on considère l'équation de Schrödinger non elliptique NES avec une non linéarité sous-critique. On démontre que le système dynamique associé à cette équation possède un attracteur global, pour des données initiales assez petites. Dans le quatrième chapitre, on reprend les problématiques de deux premiers chapitres, mais avec discrétisation en temps par un schéma de relaxation. On démontre l'existence d'un attracteur global régulier pour les systèmes dynamiques discrets associés en dimension infinieOur aim in this thesis is to study the long time behavior of the solutions to somme dissipative equations. Our work is subdivided in four chapters. In the first chapter, we consider a simplified 1-D model of a weakly damped forced Davey-Stewartson equation, which is a partial differential equation of Schrödinger type with a non local nonlinearity and with forcing and damping terms. We prove the existence of a regular global attractor for the associated dynamical system. In the second chapter, we are interested in the Davey-Stewartson system in the elliptic-elliptic case. We prove the existence and the regularity of a global attractor for sufficient small initial datas. In the third chapter, we consider the non elliptic Schrödinger equation NES with a subcritical nonlinearity. We prove that the associated dynamical system has a global attractor for sufficient small initial datas. In the fourth chapter, we go back to the issue of the first and the second chapter, but with discrete time using the relaxation scheme. We prove the existence and the regularity of a global attractor for the infinite-dimensional discrete associated dynamical systems
48
Li, Jinfeng. "Localisation d'usines et de plates-formes dans la chaîne logistique." Troyes, 2010. http://www.theses.fr/2010TROY0008.
Full textAbstract:
Cette thèse porte sur les problèmes de localisation des usines et des plates-formes dans la chaîne logistique avec trois échelons : des usines avec capacité limitée de production, des plates-formes de capacité limitée et des clients avec demandes connues. Premièrement, nous introduisons un problème de localisation de plates-formes avec flux de plusieurs-produits (LPFPP). Ce problème consiste à localiser des plates-formes, déterminer la capacité pour chaque plate-forme ouverte et organiser la livraison des produits. Un algorithme de recherche dispersée basée sur une technique d’agrégation est proposé pour résoudre le LPFPP. Deuxièmement, nous considérons un problème de localisation de plates-formes en considérant les coûts de manutention (LPFCM). Ces derniers sont modélisés de façon naturelle en intégrant à chaque plate-forme un ensemble limité de modules de manutention. Nous proposons une méthode hybride composée d’une relaxation lagrangienne, d’une décomposition pondérée de Dantzig-Wolfe et d’un path-relinking pour le LPFCM. Enfin, nous présentons un problème de localisation d’usines avec multi-flots (LUMF), qui détermine où implanter des usines et comment approvisionner des clients. Nous proposons une méthode lagrangienne couplée avec une recherche tabou pour résoudre le LUMF. Tous les algorithmes proposés dans cette thèse sont testés sur les nouveaux jeux d’essai basés sur les instances de référence provenant de la littératureThis thesis concerns the plant and transshipment point location problems in the supply chain with three layers: plants with limited production capacities, capacitated transshipment points (TPs), and customers with known demands. Firstly, we introduce a multi-capacity transshipment point location problem with multicommodity flow (LPFPP). This problem consists in locating TPs, determining the capacity for each open TP and organizing the shipments of products. A clustering-based scatter search is proposed to solve the LPFPP. Secondly, we consider a two-stage capacitated trans-shipment point location problem with handling costs (LPFCM). The latter are modeled in a realistic way by associating with each transshipment point a limited set of handling modules. We propose a hybrid method compromising a lagrangian relaxation, a weighted Dantzig-Wolfe decomposition and a path-relinking to solve the LPFCM. Lastly, we introduce a capacitated plant location problem with multicommodity flow (CLUMF) which determines where to locate plants and how to supply the clients. We propose a lagrangian-based method combined with a tabu search to solve the CLUMF. All of the proposed algorithms in this thesis are tested on new instances based on bench-marks from the literaturesa few seconds. 3) find optimal solutions for 50 bench-mark instances of TSCFLP for the first time. 4) reduce the optimality gap by 1. 2% on average for the CLRP
49
Wang, Guanglei. "Relaxations in mixed-integer quadratically constrained programming and robust programming." Thesis, Evry, Institut national des télécommunications, 2016. http://www.theses.fr/2016TELE0026/document.
Full textAbstract:
De nombreux problèmes de la vie réelle sont exprimés sous la forme de décisions à prendre à l’aide de l’information accessible dans le but d’atteindre certains objectifs. La programmation numérique a prouvé être un outil efficace pour modéliser et résoudre une grande variété de problèmes de ce type. Cependant, de nombreux problèmes en apparence faciles sont encore durs à résoudre. Et même des problèmes faciles de programmation linéaire deviennent durs avec l’incertitude de l’information disponible. Motivés par un problème de télécommunication où l’on doit associer des machines virtuelles à des serveurs tout en minimisant les coûts, nous avons employé plusieurs outils de programmation mathématique dans le but de résoudre efficacement le problème, et développé de nouveaux outils pour des problèmes plus généraux. Dans l’ensemble, résumons les principaux résultats de cette thèse comme suit. Une formulation exacte et plusieurs reformulations pour le problème d’affectation de machines virtuelles dans le cloud sont données. Nous utilisons plusieurs inégalités valides pour renforcer la formulation exacte, accélérant ainsi l’algorithme de résolution de manière significative. Nous donnons en outre un résultat géométrique sur la qualité de la borne lagrangienne montrant qu’elle est généralement beaucoup plus forte que la borne de la relaxation continue. Une hiérarchie de relaxation est également proposée en considérant une séquence de couverture de l’ensemble de la demande. Ensuite, nous introduisons une nouvelle formulation induite par les symétries du problème. Cette formulation permet de réduire considérablement le nombre de termes bilinéaires dans le modèle, et comme prévu, semble plus efficace que les modèles précédents. Deux approches sont développées pour la construction d’enveloppes convexes et concaves pour l’optimisation bilinéaire sur un hypercube. Nous établissons plusieurs connexions théoriques entre différentes techniques et nous discutons d’autres extensions possibles. Nous montrons que deux variantes de formulations pour approcher l’enveloppe convexe des fonctions bilinéaires sont équivalentes. Nous introduisons un nouveau paradigme sur les problèmes linéaires généraux avec des paramètres incertains. Nous proposons une hiérarchie convergente de problèmes d’optimisation robuste – approche robuste multipolaire, qui généralise les notions de robustesse statique, de robustesse d’affinement ajustable, et de robustesse entièrement ajustable. En outre, nous montrons que l’approche multipolaire peut générer une séquence de bornes supérieures et une séquence de bornes inférieures en même temps et les deux séquences convergent vers la valeur robuste des FARC sous certaines hypothèses modéréesMany real life problems are characterized by making decisions with current information to achieve certain objectives. Mathematical programming has been developed as a successful tool to model and solve a wide range of such problems. However, many seemingly easy problems remain challenging. And some easy problems such as linear programs can be difficult in the face of uncertainty. Motivated by a telecommunication problem where assignment decisions have to be made such that the cloud virtual machines are assigned to servers in a minimum-cost way, we employ several mathematical programming tools to solve the problem efficiently and develop new tools for general theoretical problems. In brief, our work can be summarized as follows. We provide an exact formulation and several reformulations on the cloud virtual machine assignment problem. Then several valid inequalities are used to strengthen the exact formulation, thereby accelerating the solution procedure significantly. In addition, an effective Lagrangian decomposition is proposed. We show that, the bounds providedby the proposed Lagrangian decomposition is strong, both theoretically and numerically. Finally, a symmetry-induced model is proposed which may reduce a large number of bilinear terms in some special cases. Motivated by the virtual machine assignment problem, we also investigate a couple of general methods on the approximation of convex and concave envelopes for bilinear optimization over a hypercube. We establish several theoretical connections between different techniques and prove the equivalence of two seeming different relaxed formulations. An interesting research direction is also discussed. To address issues of uncertainty, a novel paradigm on general linear problems with uncertain parameters are proposed. This paradigm, termed as multipolar robust optimization, generalizes notions of static robustness, affinely adjustable robustness, fully adjustable robustness and fills the gaps in-between. As consequences of this new paradigms, several known results are implied. Further, we prove that the multipolar approach can generate a sequence of upper bounds and a sequence of lower bounds at the same time and both sequences converge to the robust value of fully adjustable robust counterpart under some mild assumptions
50
Fokou, Pelap Géraud. "Conception d'un famework pour la relaxation des requêtes SPARQL." Thesis, Chasseneuil-du-Poitou, Ecole nationale supérieure de mécanique et d'aérotechnique, 2016. http://www.theses.fr/2016ESMA0014/document.
Full textAbstract:
Une ontologie (ou base de connaissances) est une représentation formelle de connaissances sous la forme d'entités et de faits sur ces entités. Ces dernières années de nombreuses ontologies ont été développées dans des contextes académiques et industriels. Elles sont généralement définies à l’aide du langage forme lRDF et interrogées avec le langage de requêtes SPARQL. Une connaissance partielle du contenu et de la structure d’une ontologie peut amener les utilisateurs à exécuter des requêtes qui retournent un résultat vide de réponses, considéré comme insatisfaisant. Parmi les techniques d’interrogation coopératives développées pour résoudre ce problème se trouve la technique de relaxation de requêtes. Elle consiste à affaiblir les conditions exprimées dans les requêtes pour retourner des résultats alternatifs à l'utilisateur. En étudiant les travaux existants sur la relaxation de requêtes SPARQL nous avons constaté qu’ils présentent plusieurs limitations :(1) ils ne permettent pas de définir précisément la relaxation à effectuer tout en offrant la possibilité de contrôler le processus de relaxation (2) ils n’identifient pas les causes réelles d'échec de la requête formulée par l'utilisateur et (3) ils n’intègrent pas d’outils interactifs pour mieux exploiter les techniques de relaxation proposées. Pour répondre à ces limitations, ce travail de thèse propose un framework pour la relaxation de requêtes SPARQL. Ce framework inclut un ensemble d'opérateurs de relaxation des requêtes SPARQL permettant de relaxer incrémentalement des parties précises de la requête utilisateur tout en contrôlant la pertinence des réponses alternatives retournées par rapport aux besoins exprimés par l’utilisateur dans sa requête. Notre framework propose également plusieurs algorithmes qui identifient les causes d’échec de la requête utilisateur et les requêtes qui réussissent (c'est-à-dire, qui ont des résultats) ayant un nombre maximal de conditions de la requête initialement exprimée. Ces informations permettent à l’utilisateur de mieux comprendre pourquoi sa requête échoue et d’exécuter des requêtes qui retournent des résultats alternatifs.Enfin, notre framework propose des stratégies de relaxation qui élargissent les conditions de la requête utilisateur en s’appuyant sur les causes d’échec de celle-ci. Ces stratégies permettent de réduire le temps d’exécution du processus de relaxation par rapport à l’approche classique, qui consiste à exécuter les requêtes relaxées, en fonction de leur similarité avec la requête utilisateur, jusqu’à l’obtention d’un nombre satisfaisant de résultats alternatifs. Les contributions proposées dans ce framework ont été implémentées et validées par des scénarios et expérimentations basés sur le banc d'essai LUBM. Ils montrent l’intérêt de nos contributions par rapport à l'état de l'artOntology (or Knowledge base) is a formal representation of knowledge as entities and facts related to these entities. In the past years, several ontologies have been developed in academic and industrial contexts.They are generally defined with RDF language and querying with SPARQL language. A partial knowledge of instances and schema of ontology may lead user to execute queries that result in empty answers, considered as unsatisfactory. Among cooperative querying techniques which have been developed to solve the problem of empty answers, query relaxation technique is the well-known and used. It aims at weakening the conditions expressed in the original query to return alternative answers to the user. Existing work on relaxation of SPARQL queries we suffer from many drawbacks : (1) they do not allow defining in precise way the relaxation to perform with the ability to control the relaxation process (2) they do not identify the causes of failure of the request expressed by the user and (3) they do not include interactive tools to better exploit the relaxation techniques proposed. To address these limitations, this thesis proposes an advanced framework forquery relaxation SPARQL. First, this framework includes a set of relaxation operators dedicated to SPARQLqueries, to incrementally relax specific parts of the user request while controlling the relevance of the alternative responses returned w.r.t. to the user needs expressed in his request. Our framework also provides both several algorithms that identify the causes of failure of the user query and queries that are successful with a maximum number of conditions initially expressed in the failing request. This information allows the user to better understand why his request fails and execute queries that return non-empty alternative results. Finally,our framework offers intelligent relaxation strategies that rely on the causes of query failure. Such strategies reduce the execution time of the relaxation process compared to the traditional approach, which executes relaxed requests, based on their similarity to the user request, until a number of satisfactory alternative results is obtained. All contributions proposed in this framework were implemented and validated by experiments and scenarios based on the tests bench LUBM. They show the interest of our contributions w.r.t. the state of theart