Etudes sur des problèmes de conception de réseau .Ce travail trouve sa motivation dans le grand nombre d’applications liées aux problèmes deconception de réseau, ainsi que dans leur complexités. En particulier, nous nous focalisonsur deux problèmes de conception de réseau, le Fixed Charge Uncapacitated NetworkDesign Problem with User-optimal Flow (FCNDP-UOF) et le Transmission ExpansionPlanning Problem with Redesign (TEPR). Bien qu’appartenant tout deux à la classe desproblèmes de conception de réseau, ils ont des structures différentes et spécifiques qui lesrendent intéressants.Le FCNDP-UOF est relatif au transport de produits dans les grands centres urbainset peut être modélisé comme un problème de programmation linéaire discret à deuxniveaux. Ce type de problème implique deux agents agissant simultanément plutôt queséquentiellement lors de la prise décisions. Au niveau supérieur, le leader est chargéde choisir un sous-ensemble d’arrêtes qui seront ouvertes afin de minimiser la somme descoûts fixes (d’ouverture d’arrête) et variable (de transport des commodités sur les arrêtes).Au niveau inférieur, le suiveur doit choisir un ensemble de plus courts chemins dans leréseau, par lesquels les produits seront envoyé. L’effet d’un agent sur l’autre est indirect:la décision du suiveur est affectée par le réseau conçu par le niveau supérieur, alors quela décision du leader est affectée par les coûts variables imposés par les chemins établisau niveau inférieur.Le TEPR est un problème permettant d’établir une stratégie d’expansion des réseaux detransport d’électricité en ajoutant ou supprimant des lignes de transmission. Au contrairedes autres problèmes de conception de réseau, tels que les problème des transport public,de transport de marchandises (problème de tournées de véhicules), transport de données(conception de réseau de télécommunication), l’ajout d’une ligne de transmission peutrendre impraticable une configuration qui avant etait réalisable. Cette caractéristique estdue au fait que le gestionnaire du réseau ne peut pas choisir la façon dont les lignes detransmission seront utilisées. Il ne peut agir que sur la répartition de la production etn’affecter qu’indirectement l’acheminement de l?énergie et ne peut que choisir les anglesde voltage. Cette caracteristique rend le problème a la fois très difficile et très intérêssant.L’objectif principal de cette thèse est d’étudier ces deux problèmes et de développer desalgorithmes exacts, des métaheuristiques et des méthodes hybrides. Pour le premièrproblème, on a étudié trois formulations mathemátiques, deux méthodes permettant detrouver des limites inférieures (une génération de colonnes et une heuristique) et on adéveloppé plusieurs méthodes qui ont été combinées pour obtenir une méthode de typeGRASP et une méthode de type Recherche Locale Itérative. Pour le deuxième problèmenous avons généré de nouvelles instances, développé deux nouvelles méthodes et testé cesdeux approches comme des alternatives à la résolution directe du modèle mathématique.La première méthode est une méthode de décomposition de Benders. La seconde est unecombinaison de la formulation mathématique avec un local branching.Toutes les méthodes ont été testées intensivement. Les résultats montrent l’efficacité desméthodes par rapport à l’état de l’art de chaque problème. / This thesis deals with two network design problems by means of exact, metaheuristic and hybrid techniques. The first problem studied here is the Fixed Charge Uncapacitated Network Design Problem with User-optimal Flow (FCNDP-UOF), which concerns routing multiple commodities from its origin to its destination by designing a network through selecting arcs, with an objective of minimizing the sum of the fixed costs of the selected arcs plus the sum of variable costs associated to the flows on each arc. Besides that, since the FCNDP-UOF is a bilevel problem, each commodity has to be transported through a shortest path, concerning the edges length, in the built network. To this problem existent mathematical formulations were studied and had its linear relaxations compared. After that, new heuristics and two new hybrid methods were tested. Computational experiments shows that the proposed algorithms for the FCNDP-UOF worked very well leading to a new state of the art method. The second problem studied is the Transmission Expansion Planning Problem with Redesign (TEPr), which given a new set of loads and an initial network, consists of adding or removing transmission lines in order to satisfy the new imposed loads, while minimizing the operational cost. The developed method is call Ring Partition Search and can be used as both exact and heuristic method. Computational experiments shows the impact of this method in comparison to the straight forward application of the mathematical formulation in a commercial solver. / Esta tese trata de dois problemas de planejamento de redes por meio de técnicas exatas,metaheurísticos e híbridos. O primeiro problema aqui estudado é o Problema de Planejamentode Redes com Rotas Ótimas para o Usuário (FCNDP-UOF), que diz respeitoao roteamento de múltiplos produtos desde sua origem até ao seu destino. Para realizareste roteamento uma rede é construída, minimizando a soma dos custos de adição dosarcos selecionados mais a soma dos custos variáveis associados aos fluxos em cada arco.Além disso, uma vez que o FCNDP-UOF é um problema de dois níveis, cada mercadoriatem que ser transportados por um caminho mais curto, relativo à ao comprimento dosarcos, na rede construída. Para este problema formulações matemáticas existentes foramestudadas e tiveram a força de suas relaxações lineares comparada. Depois disso, umanova heurística e dois novos métodos híbridos foram testados. Os experiências computacionaismostram que os algoritmos propostos para o FCNDP-UOF funcionam muito bemsuperando o estado da arte do problema. O segundo problema estudado é o problema dePlanejamento de Expansão de Redes de Transmissão com Redimensionamento (TEPR),que dado um novo conjunto de demandas e uma rede inicial, consiste na adição ou remoçãode linhas de transmissão, a fim de satisfazer as novas demandas impostas, minimizandoo custo operacional. Dois métodos foram desenvolvidos. O primeiro é uma decomposiçãode benders onde um conjunto de variáveis continuas é permitido no problema mestre,melhorando assim o limite da relaxação inicial. O segundo, chamado Busca Particionadaem Anéis, pode ser usado tanto como método exato e heurística. Experimentos computacionaismostraram o impacto destes métodos em comparação com a aplicação direta daformulação matemática em um solver comercial.

La recherche en génie logiciel a depuis longtemps tenté de mieux comprendre le processus de développement logiciel, minimalement, pour en reproduire les bonnes pratiques, et idéalement, pour pouvoir le mécaniser. On peut identifier deux approches majeures pour caractériser le processus. La première approche, dite transformationnelle, perçoit le processus comme une séquence de transformations préservant certaines propriétés des données à l’entrée. Cette idée a été récemment reprise par l’architecture dirigée par les modèles de l’OMG. La deuxième approche consiste à répertorier et à codifier des solutions éprouvées à des problèmes récurrents. Les recherches sur les styles architecturaux, les patrons de conception, ou les cadres d’applications s’inscrivent dans cette approche. Notre travail de recherche reconnaît la complémentarité des deux approches, notamment pour l’étape de conception: dans le cadre du développement dirigé par les modèles, nous percevons l’étape de conception comme l’application de patrons de solutions aux modèles reçus en entrée. Il est coutume de définir l’étape de conception en termes de conception architecturale, et conception détaillée. La conception architecturale se préoccupe d’organiser un logiciel en composants répondant à un ensemble d’exigences non-fonctionnelles, alors que la conception détaillée se préoccupe, en quelque sorte, du contenu de ces composants. La conception architecturale s’appuie sur des styles architecturaux qui sont des principes d’organisation permettant d’optimiser certaines qualités, alors que la conception détaillée s’appuie sur des patrons de conception pour attribuer les responsabilités aux classes. Les styles architecturaux et les patrons de conception sont des artefacts qui codifient des solutions éprouvées à des problèmes récurrents de conception. Alors que ces artefacts sont bien documentés, la décision de les appliquer reste essentiellement manuelle. De plus, les outils proposés n’offrent pas un support adéquat pour les appliquer à des modèles existants. Dans cette thèse, nous nous attaquons à la conception détaillée, et plus particulièrement, à la transformation de modèles par application de patrons de conception, en partie parce que les patrons de conception sont moins complexes, et en partie parce que l’implémentation des styles architecturaux passe souvent par les patrons de conception. Ainsi, nous proposons une approche pour représenter et appliquer les patrons de conception. Notre approche se base sur la représentation explicite des problèmes résolus par ces patrons. En effet, la représentation explicite du problème résolu par un patron permet : (1) de mieux comprendre le patron, (2) de reconnaître l’opportunité d’appliquer le patron en détectant une instance de la représentation du problème dans les modèles du système considéré, et (3) d’automatiser l’application du patron en la représentant, de façon déclarative, par une transformation d’une instance du problème en une instance de la solution. Pour vérifier et valider notre approche, nous l’avons utilisée pour représenter et appliquer différents patrons de conception et nous avons effectué des tests pratiques sur des modèles générés à partir de logiciels libres. / Software engineering researchers have long tried to understand the software process development to mechanize it or at least to codify its good practices. We identify two major approaches to characterize the process. The first approach—known as transformational—sees the process as a sequence of property-preserving transformations. This idea was recently adopted by the OMG’s model-driven architecture (MDA). The second approach consists in identifying and codifying proven solutions to recurring problems. Research on architectural styles, frameworks and design patterns are part of this approach. Our research recognizes the complementarity of these two approaches, in particular in the design step. Indeed within the model-driven development context, we view software design as the process of applying codified solution patterns to input models. Software design is typically defined in terms of architectural design and detailed design. Architectural design aims at organizing the software in modules or components that meet a set of non-functional requirements while detailed design is—in some way—concerned by the contents of the identified components. Architectural design relies on architectural styles which are principles of organization to optimize certain quality requirements, whereas detailed design relies on design patterns to assign responsibilities to classes. Both architectural styles and design patterns are design artifacts that encode proven solutions to recurring design problems. While these design artifacts are documented, the decision to apply them remains essentially manual. Besides, once a decision has been made to use a design artifact, there is no adequate support to apply it to existing models. As design patterns present an ‘‘easier’’ problem to solve, and because architectural styles implementation relies on design patterns, our strategy for addressing these issues was to try to solve the problem for design patterns first, and then tackle architectural styles. Hence, in this thesis, we propose an approach for representing and applying design patterns. Our approach is based on an explicit representation of the problems solved by design patterns. Indeed, and explicit representation of the problem solved by a pattern enables to: 1) better understand the pattern, 2) recognize the opportunity of applying the pattern by matching the representation of the problem against the models of the considered system, and 3) specify declaratively the application of the pattern as a transformation of an instance of the problem into an instance of the solution. To verify and validate the proposed approach, we used it to represent and apply several design patterns. We also conducted practical tests on models generated from open source systems.

La recherche en génie logiciel a depuis longtemps tenté de mieux comprendre le processus de développement logiciel, minimalement, pour en reproduire les bonnes pratiques, et idéalement, pour pouvoir le mécaniser. On peut identifier deux approches majeures pour caractériser le processus. La première approche, dite transformationnelle, perçoit le processus comme une séquence de transformations préservant certaines propriétés des données à l’entrée. Cette idée a été récemment reprise par l’architecture dirigée par les modèles de l’OMG. La deuxième approche consiste à répertorier et à codifier des solutions éprouvées à des problèmes récurrents. Les recherches sur les styles architecturaux, les patrons de conception, ou les cadres d’applications s’inscrivent dans cette approche. Notre travail de recherche reconnaît la complémentarité des deux approches, notamment pour l’étape de conception: dans le cadre du développement dirigé par les modèles, nous percevons l’étape de conception comme l’application de patrons de solutions aux modèles reçus en entrée. Il est coutume de définir l’étape de conception en termes de conception architecturale, et conception détaillée. La conception architecturale se préoccupe d’organiser un logiciel en composants répondant à un ensemble d’exigences non-fonctionnelles, alors que la conception détaillée se préoccupe, en quelque sorte, du contenu de ces composants. La conception architecturale s’appuie sur des styles architecturaux qui sont des principes d’organisation permettant d’optimiser certaines qualités, alors que la conception détaillée s’appuie sur des patrons de conception pour attribuer les responsabilités aux classes. Les styles architecturaux et les patrons de conception sont des artefacts qui codifient des solutions éprouvées à des problèmes récurrents de conception. Alors que ces artefacts sont bien documentés, la décision de les appliquer reste essentiellement manuelle. De plus, les outils proposés n’offrent pas un support adéquat pour les appliquer à des modèles existants. Dans cette thèse, nous nous attaquons à la conception détaillée, et plus particulièrement, à la transformation de modèles par application de patrons de conception, en partie parce que les patrons de conception sont moins complexes, et en partie parce que l’implémentation des styles architecturaux passe souvent par les patrons de conception. Ainsi, nous proposons une approche pour représenter et appliquer les patrons de conception. Notre approche se base sur la représentation explicite des problèmes résolus par ces patrons. En effet, la représentation explicite du problème résolu par un patron permet : (1) de mieux comprendre le patron, (2) de reconnaître l’opportunité d’appliquer le patron en détectant une instance de la représentation du problème dans les modèles du système considéré, et (3) d’automatiser l’application du patron en la représentant, de façon déclarative, par une transformation d’une instance du problème en une instance de la solution. Pour vérifier et valider notre approche, nous l’avons utilisée pour représenter et appliquer différents patrons de conception et nous avons effectué des tests pratiques sur des modèles générés à partir de logiciels libres. / Software engineering researchers have long tried to understand the software process development to mechanize it or at least to codify its good practices. We identify two major approaches to characterize the process. The first approach—known as transformational—sees the process as a sequence of property-preserving transformations. This idea was recently adopted by the OMG’s model-driven architecture (MDA). The second approach consists in identifying and codifying proven solutions to recurring problems. Research on architectural styles, frameworks and design patterns are part of this approach. Our research recognizes the complementarity of these two approaches, in particular in the design step. Indeed within the model-driven development context, we view software design as the process of applying codified solution patterns to input models. Software design is typically defined in terms of architectural design and detailed design. Architectural design aims at organizing the software in modules or components that meet a set of non-functional requirements while detailed design is—in some way—concerned by the contents of the identified components. Architectural design relies on architectural styles which are principles of organization to optimize certain quality requirements, whereas detailed design relies on design patterns to assign responsibilities to classes. Both architectural styles and design patterns are design artifacts that encode proven solutions to recurring design problems. While these design artifacts are documented, the decision to apply them remains essentially manual. Besides, once a decision has been made to use a design artifact, there is no adequate support to apply it to existing models. As design patterns present an ‘‘easier’’ problem to solve, and because architectural styles implementation relies on design patterns, our strategy for addressing these issues was to try to solve the problem for design patterns first, and then tackle architectural styles. Hence, in this thesis, we propose an approach for representing and applying design patterns. Our approach is based on an explicit representation of the problems solved by design patterns. Indeed, and explicit representation of the problem solved by a pattern enables to: 1) better understand the pattern, 2) recognize the opportunity of applying the pattern by matching the representation of the problem against the models of the considered system, and 3) specify declaratively the application of the pattern as a transformation of an instance of the problem into an instance of the solution. To verify and validate the proposed approach, we used it to represent and apply several design patterns. We also conducted practical tests on models generated from open source systems.