101 |
The Reliability Assessment and Optimization of Arbitrary-State Monotone Systems under Epistemic Uncertainty / L'évaluation et L'optimisation De La Fiabilité Des Systèmes Monotones et à Etat arbitraire Sous Incertitude ÉpistémiqueSun, Muxia 03 July 2019 (has links)
Dans ce travail, nous étudions l’évaluation de la fiabilité, la modélisation et l’optimisation de systèmes à états arbitraires à incertitude épistémique. Tout d'abord, une approche universelle de modélisation à l'état arbitraire est proposée afin d'étudier efficacement les systèmes industriels modernes aux structures, mécanismes de fonctionnement et exigences de fiabilité de plus en plus complexes. De simples implémentations de modèles de fiabilité binaires, continus ou multi-états traditionnels ont montré leurs lacunes en termes de manque de généralité lors de la modélisation de structures, systèmes, réseaux et systèmes de systèmes industriels modernes et complexes. Dans ce travail, nous intéressons aussi particulièrement aux systèmes monotones, non seulement parce que la monotonie est apparue couramment dans la plupart des modèles de fiabilité standard, mais aussi qu’une propriété mathématique aussi simple permet une simplification énorme de nombreux problèmes extrêmement complexes. Ensuite, pour les systèmes de fiabilité monotones à états arbitraires, nous essayons de résoudre les problèmes suivants, qui sont apparus dans les principes mêmes de la modélisation mathématique: 1. L’évaluation de la fiabilité dans un environnement incertain épistémique avec des structures hiérarchiques être exploitées par toute approche de programmation 2; l'optimisation de la fiabilité / maintenance pour les systèmes à grande fiabilité avec incertitude épistémique. / In this work, we study the reliability assessment, modeling and optimization of arbitrary-state systems with epistemic uncertainty. Firstly, a universal arbitrary-state modelling approach is proposed, in order to effectively study the modern industrial systems with increasingly complicated structures, operation mechanisms and reliability demands. Simple implementations of traditional binary, continuous or multi-state reliability models have been showing their deficiencies in lack of generality, when modelling such complex modern industrial structures, systems, networks and systems-of-systems. In this work, we are also particularly interested in monotone systems, not only because monotonicity commonly appeared in most of the standard reliability models, but also that such a simple mathematical property allows a huge simplification to many extremely complex problems. Then, for the arbitrary-state monotone reliability systems, we try to solve the following challenges that appeared in its very fundamentals of mathematical modeling: 1. The reliability assessment under epistemic uncertain environment with hierarchy structures; 2. The reliability/maintenance optimization for large reliability systems under epistemic uncertainty.
|
102 |
Evaluating the utility of short-term hydrological forecasts in a hydropower systemNikghalb Ashouri, Hajar 26 January 2019 (has links)
Le fonctionnement optimal d'un système de réservoirs est un processus décisionnel complexe impliquant, entre autres, l'identication d'un compromis temporel concernant l'utilisation de l'eau : la dernière unité d'eau doit-elle être conservée ou plutôt utilisée pour un usage immédiat? La variabilité des apports hydrologiques complique encore davantage ce processus décisionnel puisque la recherche de ce compromis doit être effectuée sans une connaissance parfaite des conditions futures. De manière générale, l'équilibre optimal entre les utilisations immédiates et futures de l'eau nécessite l'intégration de règles de gestion à court et à long terme. Si les règles à court terme conduisent à des décisions à courte vue, les stratégies opérationnelles à long terme ne sont pas appropriées pour gérer des événements à court terme tels que les inondations. Nous proposons un cadre de modélisation basé sur l'approche de décomposition temporelle (DT) : Les stratégies à moyen/long terme sont tout d'abord déterminées puis utilisées comme limites pour l'optimisation des stratégies à court terme. Le modèle d'optimisation à moyen terme capture la persistance temporelle trouvée dans le processus des apports hydrologiques hebdomadaires, alors que les prévisions hydrologiques d'ensemble (PHE) sont utilisées pour piloter le modèle à court terme sur un pas de temps journalier. Plus spécifiquement, la programmation dynamique stochastique duale (SDDP) génère les fonctions des bénéces de valeur hebdomadaires qui sont ensuite imposées à un modèle de programmation linéaire implémenté sur chaque membre des PHE de 14 jours. Ce cadre de modélisation est mis en oeuvre selon un mode de gestion en horizon roulant sur une cascade de centrales hydroélectriques dans le bassin de la rivière Gatineau dans la province du Québec au Canada. À l'aide de ce cadre de modélisation, nous analysons la relation entre la valeur économique et les caractéristiques statistiques des PHE. Les résultats montrent que l'énergie générée par le système hydroélectrique augmente avec la précision et la résolution de la prévision, mais que la relation n'est pas univoque. En effet, d'autres facteurs semblent contribuer à l'utilité de la prévision / The optimal operation of a system of reservoirs is a complex decision-making problem involving, among others, the identification of a temporal trade-offs regarding the use of water. Should the last unit of water be kept in storage or rather be released for use downstream? The variability of natural inflows further complicates this decision-making problem: at any given point in space and time, this trade-off must be made without a perfect knowledge of future reservoir in flows. Generally speaking, the optimal balance between immediate and future uses of water requires the integration of short- and long-term policies. If short-term policies lead to shortsighted decisions, long-term operational strategies are not appropriate to handle short-term events such as floods. We propose a modeling framework based on the time decomposition (TD) approach: mid/long-term policies are determined first and then used as boundary conditions for the optimization of short-term policies. The mid-term optimization model captures the temporal persistence found in the weekly streamflow process whereas Ensemble Streamflow Forecasts (ESF) are used to drive the short-term model on a daily time step. More specifically, a Stochastic Dual Dynamic Programming (SDDP) generates the weekly benefit-to-go functions that are then imposed to a linear programming model implemented on each 14-days member of the ESF. This modelling framework is implemented in a rolling-horizon mode on a cascade of hydropower stations in the Gatineau River basin, Quebec, Canada. Using this modelling framework, we analyze the relationship between the economic value of different sets of short-term hydrologic forecasts. The results show that the energy generated by the hydropower system increases with the forecast's accuracy and resolution but that the relationship is not univocal; other factors seem to contribute to the forecast's utility.
|
103 |
Optimisation stochastique des systèmes multi-réservoirs par l'agrégation de scénarios et la programmation dynamique approximativeZéphyr, Luckny 23 April 2018 (has links)
Les problèmes de gestion des réservoirs sont stochastiques principalement à cause de l’incertitude sur les apports naturels. Ceci entraine des modèles d’optimisation de grande taille pouvant être difficilement traitables numériquement. La première partie de cette thèse réexamine la méthode d’agrégation de scénarios proposée par Rockafellar et Wets (1991). L’objectif consiste à améliorer la vitesse de convergence de l’algorithme du progressive hedgging sur lequel repose la méthode. L’approche traditionnelle consiste à utiliser une valeur fixe pour ce paramètre ou à l’ajuster selon une trajectoire choisie a priori : croissante ou décroissante. Une approche dynamique est proposée pour mettre à jour le paramètre en fonction d’information sur la convergence globale fournie par les solutions à chaque itération. Il s’agit donc d’une approche a posteriori. La thèse aborde aussi la gestion des réservoirs par la programmation dynamique stochastique. Celle-ci se prête bien à ces problèmes de gestion à cause de la nature séquentielle de leurs décisions opérationnelles. Cependant, les applications sont limitées à un nombre restreint de réservoirs. La complexité du problème peut augmenter exponentiellement avec le nombre de variables d’état, particulièrement quand l’approche classique est utilisée, i.e. en discrétisant l’espace des états de « manière uniforme ». La thèse propose une approche d’approximation sur une grille irrégulière basée sur une décomposition simpliciale de l’espace des états. La fonction de valeur est évaluée aux sommets de ces simplexes et interpolée ailleurs. À l’aide de bornes sur la vraie fonction, la grille est raffinée tout en contrôlant l’erreur d’approximation commise. En outre, dans un contexte décision-information spécifique, une hypothèse « uni-bassin », souvent utilisée par les hydrologues, est exploitée pour développer des formes analytiques pour l’espérance de la fonction de valeur. Bien que la méthode proposée ne résolve pas le problème de complexité non polynomiale de la programmation dynamique, les résultats d’une étude de cas industrielle montrent qu’il n’est pas forcément nécessaire d’utiliser une grille très dense pour approximer la fonction de valeur avec une précision acceptable. Une bonne approximation pourrait être obtenue en évaluant cette fonction uniquement en quelques points de grille choisis adéquatement. / Reservoir operation problems are in essence stochastic because of the uncertain nature of natural inflows. This leads to very large optimization models that may be difficult to handle numerically. The first part of this thesis revisits the scenario aggregation method proposed by Rochafellar and Wets (1991). Our objective is to improve the convergence of the progressive hedging algorithm on which the method is based. This algorithm is based on an augmented Lagrangian with a penalty parameter that plays an important role in its convergence. The classical approach consists in using a fixed value for the parameter or in adjusting it according a trajectory chosen a priori: decreasing or increasing. This thesis presents a dynamic approach to update the parameter based on information on the global convergence provided by the solutions at each iteration. Therefore, it is an a posteriori scheme. The thesis also addresses reservoir problems via stochastic dynamic programming. This scheme is widely used for such problems because of the sequential nature of the operational decisions of reservoir management. However, dynamic programing is limited to a small number of reservoirs. The complexity may increase exponentially with the dimension of the state variables, especially when the classical approach is used, i.e. by discretizing the state space into a "regular grid". This thesis proposes an approximation scheme over an irregular grid based on simplicial decomposition of the state space. The value function is evaluated over the vertices of these simplices and interpolated elsewhere. Using bounds on the true function, the grid is refined while controlling the approximation error. Furthermore, in a specific information-decision context, a "uni-bassin" assumption often used by hydrologists is exploited to develop analytical forms for the expectation of the value function. Though the proposed method does not eliminate the non-polynomial complexity of dynamic programming, the results of an industrial case study show that it is not absolutely necessary to use a very dense grid to appropriately approximate the value function. Good approximation may be obtained by evaluating this function at few appropriately selected grid points.
|
104 |
Sub-optimal Energy Management Architecture for Intelligent Hybrid Electric Bus : Deterministic vs. Stochastic DP strategy in Urban Conditions / Architecture de gestion de l'énergie sous-optimale pour les bus électriques hybrides intelligents : stratégie basée DP déterministe versus stratégie basée DP stochastique en milieu urbainAbdrakhmanov, Rustem 27 June 2019 (has links)
Cette thèse propose des stratégies de gestion de l'énergie conçues pour un bus urbain électrique hybride. Le système de commande hybride devrait créer une stratégie efficace de coordination du flux d’énergie entre le moteur thermique, la batterie, les moteurs électriques et hydrauliques. Tout d'abord, une approche basée sur la programmation dynamique déterministe (DDP) a été proposée : algorithme d'optimisation simultanée de la vitesse et de la puissance pour un trajet donné (limité par la distance parcourue et le temps de parcours). Cet algorithme s’avère être gourmand en temps de calcul, il n’a pas été donc possible de l’utiliser en temps réel. Pour remédier à cet inconvénient, une base de données de profils optimaux basée sur DP (OPD-DP) a été construite pour une application en temps réel. Ensuite, une technique de programmation dynamique stochastique (SDP) a été utilisée pour générer simultanément et d’une manière optimale un profil approprié de la vitesse du Bus ainsi que sa stratégie de partage de puissance correspondante. Cette approche prend en compte à la fois la nature stochastique du comportement de conduite et les conditions de circulations urbaines (soumises à de multiples aléas). Le problème d’optimisation énergétique formulé, en tant que problème intrinsèquement multi-objectif, a été transformé en plusieurs problèmes à objectif unique avec contraintes utilisant une méthode ε-constraint afin de déterminer un ensemble de solutions optimales (le front de Pareto).En milieu urbain, en raison des conditions de circulation, des feux de circulation, un bus rencontre fréquemment des situations Stop&Go. Cela se traduit par une consommation d'énergie accrue lors notamment des démarrages. En ce sens, une stratégie de régulation de vitesse adaptative adaptée avec Stop&Go (eACCwSG) apporte un avantage indéniable. L'algorithme lisse le profil de vitesse pendant les phases d'accélération et de freinage du Bus. Une autre caractéristique importante de cet algorithme est l’aspect sécurité, étant donné que l’ACCwSG permet de maintenir une distance de sécurité afin d’éviter les collisions et d’appliquer un freinage en douceur. Comme il a été mentionné précédemment, un freinage en douceur assure le confort des passagers. / This PhD thesis proposes Energy Management Strategies conceived for a hybrid electrical urban bus. The hybrid control system should create an efficient strategy of coordinating the flow of energy between the heat engine, battery, electrical and hydraulic motors. Firstly, a Deterministic Dynamic Programming (DDP) based approach has been proposed: simultaneous speed and powersplit optimization algorithm for a given trip (constrained by the traveled distance and time limit). This algorithm turned out to be highly time consuming so it cannot be used in real-time. To overcome this drawback, an Optimal Profiles Database based on DP (OPD-DP) has been constructed for real-time application. Afterwards, a Stochastic Dynamic Programming (SDP) technique is used to simultaneously generate an optimal speed profile and related powersplit strategy. This approach takes into account a stochastic nature of the driving behavior and urban conditions. The formulated energy optimization problem, being intrinsically multi-objective problem, has been transformed into several single-objective ones with constraints using an ε-constraint method to determine a set of optimal solutions (the Pareto Front).In urban environment, due to traffic conditions, traffic lights, a bus encounters frequent Stop&Go situations. This results in increased energy consumption during the starts. In this sense, a relevant Eco Adaptive Cruise Control with Stop&Go (eACCwSG) strategy brings the undeniable benefit. The algorithm smooths speed profile during acceleration and braking phases. One more important feature of this algorithm is the safety aspect, as eACCwSG permits to maintain a safety distance in order to avoid collision and apply a smooth braking. As it was mentioned before, smooth braking ensures passengers comfort.
|
105 |
A dynamic sequential route choice model for micro-simulationMorin, Léonard Ryo 09 1900 (has links)
Dans les études sur le transport, les modèles de choix de route décrivent la sélection par un utilisateur d’un chemin, depuis son origine jusqu’à sa destination. Plus précisément, il s’agit de trouver dans un réseau composé d’arcs et de sommets la suite d’arcs reliant deux sommets, suivant des critères donnés. Nous considérons dans le présent travail l’application de la programmation dynamique pour représenter le processus de choix, en considérant le choix d’un chemin comme une séquence de choix d’arcs. De plus, nous mettons en œuvre les techniques d’approximation en programmation dynamique afin de représenter la connaissance imparfaite de l’état réseau, en particulier pour les arcs éloignés du point actuel. Plus précisément, à chaque fois qu’un utilisateur atteint une intersection, il considère l’utilité d’un certain nombre d’arcs futurs, puis une estimation est faite pour le restant du chemin jusqu’à la destination. Le modèle de choix de route est implanté dans le cadre d’un modèle de simulation de trafic par événements discrets. Le modèle ainsi construit est testé sur un modèle de réseau routier réel afin d’étudier sa performance. / In transportation modeling, a route choice is a model describing the selection of a route between a given origin and a given destination. More specifically, it consists of determining the sequence of arcs leading to the destination in a network composed of vertices and arcs, according to some selection criteria. We propose a novel route choice model, based on approximate dynamic programming. The technique is applied sequentially, as every time a user reaches an intersection, he/she is supposed to consider the utility of a certain number of future arcs, followed by an approximation for the rest of the path leading up to the destination. The route choice model is implemented as a component of a traffic simulation model, in a discrete event framework. We conduct a numerical experiment on a real traffic network model in order to analyze its performance.
|
106 |
Une signature du polymorphisme structural d’acides ribonucléiques non-codants permettant de comparer leurs niveaux d’activités biochimiquesDallaire, Paul 05 1900 (has links)
Des évidences expérimentales récentes indiquent que les ARN changent de structures au fil du temps, parfois très rapidement, et que ces changements sont nécessaires à leurs activités biochimiques. La structure de ces ARN est donc dynamique. Ces mêmes évidences notent également que les structures clés impliquées sont prédites par le logiciel de prédiction de structure secondaire MC-Fold.
En comparant les prédictions de structures du logiciel MC-Fold, nous avons constaté un lien clair entre les structures presque optimales (en termes de stabilité prédites par ce logiciel) et les variations d’activités biochimiques conséquentes à des changements ponctuels dans la séquence.
Nous avons comparé les séquences d’ARN du point de vue de leurs structures dynamiques afin d’investiguer la similarité de leurs fonctions biologiques. Ceci a nécessité une accélération notable du logiciel MC-Fold. L’approche algorithmique est décrite au chapitre 1. Au chapitre 2 nous classons les impacts de légères variations de séquences des microARN sur la fonction naturelle de ceux-ci. Au chapitre 3 nous identifions des fenêtres dans de longs ARN dont les structures dynamiques occupent possiblement des rôles dans les désordres du spectre autistique et dans la polarisation des œufs de certains batraciens (Xenopus spp.). / Recent experimental evidence indicates that RNA structure changes, sometimes very rapidly and that these changes are both required for biochemical activity and captured by the secondary structure prediction software MC-Fold. RNA structure is thus dynamic.
We compared RNA sequences from the point of view of their structural dynamics so as to investigate how similar their biochemical activities were by computing a signature from the output of the structure prediction software MC-Fold.
This required us to accelerate considerably the software MC-Fold. The algorithmic approach to this acceleration is described in chapter 1. In chapter 2, point mutations that disrupt the biochemical activity of microRNA are explained in terms of changes in RNA dynamics. Finally, in chapter 3 we identify dynamic structure windows in long RNA with potentially significant roles in autism spectrum disorders and separately in Xenopus ssp. (species of frogs) egg polarisation.
|
107 |
Dynamique des populations : contrôle stochastique et modélisation hybride du cancer / Population dynamics : stochastic control and hybrid modelling of cancerClaisse, Julien 04 July 2014 (has links)
L'objectif de cette thèse est de développer la théorie du contrôle stochastique et ses applications en dynamique des populations. D'un point de vue théorique, nous présentons l'étude de problèmes de contrôle stochastique à horizon fini sur des processus de diffusion, de branchement non linéaire et de branchement-diffusion. Dans chacun des cas, nous raisonnons par la méthode de la programmation dynamique en veillant à démontrer soigneusement un argument de conditionnement analogue à la propriété de Markov forte pour les processus contrôlés. Le principe de la programmation dynamique nous permet alors de prouver que la fonction valeur est solution (régulière ou de viscosité) de l'équation de Hamilton-Jacobi-Bellman correspondante. Dans le cas régulier, nous identifions également un contrôle optimal markovien par un théorème de vérification. Du point de vue des applications, nous nous intéressons à la modélisation mathématique du cancer et de ses stratégies thérapeutiques. Plus précisément, nous construisons un modèle hybride de croissance de tumeur qui rend compte du rôle fondamental de l'acidité dans l'évolution de la maladie. Les cibles de la thérapie apparaissent explicitement comme paramètres du modèle afin de pouvoir l'utiliser comme support d'évaluation de stratégies thérapeutiques. / The main objective of this thesis is to develop stochastic control theory and applications to population dynamics. From a theoritical point of view, we study finite horizon stochastic control problems on diffusion processes, nonlinear branching processes and branching diffusion processes. In each case we establish a dynamic programmic principle by carefully proving a conditioning argument similar to the strong Markov property for controlled processes. Then we deduce that the value function is a (viscosity or regular) solution of the associated Hamilton-Jacobi-Bellman equation. In the regular case, we further identify an optimal control in the class of markovian strategies thanks to a verification theorem. From a pratical point of view, we are interested in mathematical modelling of cancer growth and treatment. More precisely, we build a hybrid model of tumor growth taking into account the essential role of acidity. Therapeutic targets appear explicitly as model parameters in order to be able to evaluate treatment strategies.
|
108 |
Problèmes de commande optimale stochastique généralisésZitouni, Foued 11 1900 (has links)
No description available.
|
109 |
Conception de solutions exactes pour la fabrication de "vias" en utilisant la technologie DSA / Design of exact solutions for the manufacturing of "vias" using DSA technologyAit ferhat, Dehia 15 October 2018 (has links)
Maitriser les coûts de fabrication des circuits intégrés tout en augmentant leur densité est d'une importance primordiale pour maintenir une certaine rentabilité dans l’industrie du semi-conducteur. Parmi les différents composants d’un circuit, nous nous intéressons aux connections verticales et métalliques, connues sous le nom de « vias ». Durant la fabrication, un processus de lithographie complexe est utilisé pour former une disposition de vias est formée sur une plaque de silicium, à l’aide d’un un masque optique. Pour des raisons de fabrication, une distance minimum entre les vias doit être respectée. Lorsque cette distance n’est pas respectée, nous parlons de « conflit ». Afin de supprimer ces conflits, l’industrie utilise une technique qui permet de décomposer une disposition de vias cible en plusieurs sous-ensembles, où les contraintes de distance minimum sont respectées : la formation des sous-ensembles individuels se fait en séquence sur la plaque de silicium en utilisant un masque optique par sous-ensemble. Cette technique est appelée Multiple Patterning (MP). Il y a de nombreuses façons de décomposer une disposition de vias et le but est d’assigner les vias à un nombre minimum de masques, car les masques sont coûteux. Minimiser le nombre de masques est équivalent à minimiser le nombre de couleurs dans un graphe disque unitaire. Ce problème est NP-difficile, mais un certain nombre de « bonnes » heuristiques existent. Une technique récente et prometteuse basée sur l’auto-assemblage et direction des molécules, aussi connue sous le nom Directed Self Assembly (DSA), permet de grouper les vias en conflits à condition de respecter certaines contraintes. L’objectif est de trouver la meilleure façon de grouper les vias afin de minimiser le nombre de masques tout en respectant les contraintes liées à DSA. Ce problème est un problème de coloration de graphes où les sommets de chaque couleurs définissent un ensemble de chemins « indépendants » de longueurs au plus k que nous appelons aussi le problème de coloration par k-chemins. Durant la modélisation, nous avons distingué deux problèmes de coloration par k-chemins pertinents: le problème général et le problème induit. Les deux problèmes sont connus pour être NP-difficile, ce qui explique l’utilisation d’heuristiques dans l’industrie pour trouver une décomposition valide en sous-ensembles. Dans cette étude, nous nous intéressons à des méthodes exactes afin de concevoir des solutions optimales et d’évaluer la qualité de l’heuristique développée en industrie (chez Mentor Graphics). Nous présentons différentes méthodes: une approche par programmation linéaire en nombre entier (ILP) où nous étudions plusieurs formulations, une approche par programmation dynamique pour résoudre le cas induit quand k=1 ou k=2 et lorsque les graphes ont une petite longueur arborescente ; enfin, nous étudions le cas particulier des graphes lignes. Les résultats des différentes études numériques montrent que les formulations ILP « naïves » sont les meilleures. Elles listent tous les chemins possibles de longueur au plus k. Les tests sur des données industrielles ayant au plus 2000 sommets (plus grande composante connexe parmi celles qui constituent une instance) ont montré que les deux problèmes, général et induit, sont résolus en moins de 6 secondes, pour k=1 et k=2. La programmation dynamique, appliquée au problème induit de coloration par k-chemins quand k=1 et k=2, montre des résultats équivalents à ceux de la formulation ILP naïve. Cependant, nous nous attendons à de meilleurs résultats par programmation dynamique quand la valeur de k augmente. Enfin, nous montrons qu’un cas particuliers des graphes lignes peut être résolu en temps polynomial en exploitant les propriétés de l’algorithme d'Edmonds et des couplages dans les graphes bipartis. / Controlling the manufacturing costs of integrated circuits while increasing their density is of a paramount importance to maintain a certain degree of profitability in the semi-conductor industry. Among various components of a circuit, we are interested in vertical metallic connections known as “vias”. During manufacturing, a complex lithography process is used to form an arrangement of vias on a silicon wafer support, using an optical mask. For manufacturing reasons, a minimum distance between the vias must be respected. Whenever this is not the case, we are talking about a “conflict”. In order to eliminate these conflicts, the industry uses a technique that decomposes an arrangement of vias in several subsets, where minimum distance constraints are respected: the formation of the individual subsets is done, in sequence, on a silicon wafer using one optical mask per subset. This technique is called Multiple Patterning (MP). There are several ways to decompose an arrangement of vias, the goal being to assign the vias to a minimum number of masks, since the masks are expensive. Minimizing the number of masks is equivalent to minimizing the number of colors in a unit disk graph. This is a NP-hard problem however, a number of “good” heuristics exist. A recent and promising technique is based on the direction and self-assembly of the molecules called Directed Self Assembly (DSA), allows to group vias in conflict according to certain conditions. The main challenge is to find the best way of grouping vias to minimize the number of masks while respecting the constraints related to DSA. This problem is a graph coloring problem where the vertices within each color define a set of independent paths of length at most k also called a k-path coloring problem. During the graph modeling, we distinguished two k-path coloring problems: a general problem and an induced problem. Both problems are known to be NP-hard, which explains the use of heuristics in the industry to find a valid decomposition into subsets. In this study, we are interested in exact methods to design optimal solutions and evaluate the quality of heuristics developed in the industry (at Mentor Graphics). We present different methods: an integer linear programming (ILP) approach where we study several formulations, a dynamic programming approach to solve the induced case when k=1 or k=2 and when the graphs have small tree-width; finally, we study a particular case of line graphs. The results of the various numerical studies show that the naïve ILP formulations are the best, they list all possible paths of length at most k. Tests on a snippet of industrial instances of at most 2000 vertices (a largest connected component among those constituting an instance) have shown that the two problems, general and induced, are solved in less than 6 seconds, for k=1 and k=2. Dynamic programming, applied to the induced k-path coloring when k=1 and k=2, shows results equivalent to those of the naïve ILP formulation, but we expect better results by dynamic programming when the value of k increases. Finally, we show that the particular case of line graphs can be solved in polynomial time by exploiting the properties of Edmonds’ algorithm and bipartite matching.
|
110 |
Régulation de la qualité lors de la transmission de contenus vidéo sur des canaux sans fils / Quality-oriented control of video delivery over wireless channelsChanguel, Nesrine 14 December 2011 (has links)
Le développement simultané de terminaux mobiles multimédia (smartphones, tablettes) et de réseaux d’accès offrant des débits élevés conduit à une explosion du trafic liés aux contenus multimédia. Cette croissance nécessite un partage efficace des ressources radio entre fournisseurs de contenus (dans le cas de la diffusion) ou entre récepteurs (dans le cas de services de vidéo à la demande). Cette thèse propose des outils de partage équitable des ressources en termes de qualité des contenus multimédia reçu et de délai de transmission dans les deux contextes précédents. La variété des compromis débit-distorsion des contenus multimédia est exploitée à cet effet. Dans un premier temps, une solution centralisée de contrôle conjoint du débit de codage et de transmission de plusieurs programmes transmis sur un même canal est considérée. L’objectif est de fournir des flux de qualités similaires avec des variations limitées, tout en assurant des délais de transmission comparables. Ce problème est résolu en synthétisant une commande prédictive à l’aide d’outils d’optimisation sous contrainte. Dans un second temps, seule l’allocation de bande est centralisée, le contrôle des caractéristiques de compression de chaque flux est réalisé de manière distribuée. Le contrôleur centralisé ne renvoie que le niveau de remplissage des tampons associés à chaque flux aux fournisseurs de contenus distants. Une stratégie de régulation des débits de codage est alors mise en place par ces fournisseurs, de manière à réguler le niveau en bits ou en image des tampons. La stabilité de ce système de régulation couplé est étudiée en détails. Enfin, l’optimisation inter-couches d’une chaine de transmission de contenus multimédia scalable est considérée. Ce problème est formulé dans le contexte de la programmation dynamique. Lorsque des modèles de complexité raisonnable sont considérés et avec des caractéristiques du système bien connues, des solutions optimales peuvent être obtenues. Des techniques d’apprentissage sont mises en œuvre, lorsque le système n’est que partiellement connu, par exemple, lorsque l’état du canal de transmission parvient avec du retard à l’organe de commande. / Due to the emergence of new generation mobiles and media streaming services, data traffic on mobile networks is continuously exploding. Despite the emergence of standards such as LTE, resources still remain scarce and limited. Thus, efficiently sharing resources among broadcasters or between unicast receivers connected to the same base station is necessary. An efficient resources allocation, where a fair received video quality between users and an equal transmission delay are achieved, is targeted. To that end, the variety of the rate-distortion trade-off of multimedia content is exploited. First, a centralized joint encoding and transmission rate control of multiple programs sharing the same channel is considered. A satisfactory and a comparable video quality among the transmitted programs, with limited variations, as well as a comparable transmission delay are targeted. The problem is solved using constrained optimization tools. Second, only the bandwidth allocation control is centralized, the control of the encoding rate characteristics of each stream is carried in a distributed manner. By modeling the problem as a feedback control system, the centralized bandwidth allocation is required to feed back only the buffer level to its associated remote content provider. The equilibrium and stability issues are addressed for both bit and second buffer control. In the case of simple unicast connection, a cross-layer optimization of scalable video delivery over wireless channel is performed. The optimization problem is cast in the context of dynamic programming. When low complex model are considered and when the system characteristics are known, optimal solutions can be obtained. When the system is partially known, for example, when the state of the channel reaches the control process with delay, learning techniques are implemented.
|
Page generated in 0.0759 seconds