Search

This thesis addresses a class of bi-level network design problems. We are interested in investigating applications from different domains and in developing exact algorithms to solve the corresponding bi-level network problem. In particular, we study a bi-level network design problem where the leader selects a part of the network to be activated, then, in the second level, the solution must be optimal for a network flow problem in the selected sub-network. In this thesis, three applications of this problem are studied: hazmats transportation, telecommunication, and social networks analysis. The second level problem in the first and the last applications is a shortest path problem while a minimum cost flow is required in the second application.The first studied problem is the fixed charge network design problem with shortest path constraints, which is modeled as a bi-level program and can be applied in hazardous transportation. For this problem, we propose two new binary integer programming (BILP) formulations inspired by path and cycle inequalities. We incorporate these formulations in a branch-and-cut algorithm and another cutting-plane based method. Numerical experiments are performed on real instances, and random data sets generated with different criteria to examine the difficulty of the instances. The results show that the proposed cutting plane algorithms can solve up to 19% more instances than the compact formulations.The second studied problem is the energy-aware traffic engineering while using multi-path routing to minimize link capacity utilization in ISP backbone networks. We propose a bi-level optimization model where the upper level represents the energy management function, and the lower one refers to the deployed multi-path routing protocol. Then, we reformulate it as a one-level MILP replacing the second level problem by different sets of flow optimality conditions. We further use these formulations to solve the problem with classical cutting plane and branch-and-cut algorithms. The computational experiments are performed on real instances to compare the proposed algorithms and to evaluate the efficiency of our model against existing single-path and multi-objective models.Finally, we study the problem of maximization influence in signed social networks. To the best of our knowledge, it is the first time that this problem is modeled as a bi-level programming problem. We reformulate the problem as one-level MILP models using three different optimality conditions of the shortest path problem appearing in the second level. These formulations are strengthened by adding a set of valid inequalities. Computational experiments are performed using random instances to compare the different proposed formulations. Finally, explicit solutions and bounds are proposed for particular cases of instances.; Cette thèse s'adresse à la classe des problèmes de conception de réseaux bi-niveaux. Nous nous sommes intéressés à l'étude des applications des différents domaines et au développement d'algorithmes exacts pour la résolution des problème de réseaux bi-niveau correspondants. En particulier, nous avons étudié le problème de conception de réseau bi-niveau dans lequel le ``leader" sélectionne une partie du réseau à activer, puis, dans le deuxième niveau, la solution doit être optimale pour un problème de flot dans le sous-réseau sélectionné. Dans cette thèse, trois applications de ce problème sont étudiées : le transport de matières dangereuses, les réseaux de télécommunication et les réseaux sociaux. Le problème de deuxième niveau dans la première et la dernière application est un problème de plus court chemin alors qu'un flot de coûts minimum est requis dans la deuxième application.Le premier problème étudié est le problème de conception de réseau avec coût fixe avec contraintes de plus court chemin. Le problème est modélisé comme un programme bi-niveaux qui peut être appliqué dans le transport des matières dangereuses. Pour ce problème, nous proposons deux nouvelles formulations de programmation en nombres entiers (PLNE) inspirées par des inégalités de chemin et de cycle. Nous incorporons ces formulations dans des algorithmes de branch-and-cut et de plans coupants. Des tests numériques sont effectués sur des instances réelles et sur un ensembles d'instances aléatoires qui sont générées avec différents critères pour examiner la difficulté de ces instances. Les résultats montrent que les algorithmes de plan coupants proposés peuvent résoudre jusqu’à 19% d’instances de plus que les formulations compactes.Le deuxième problème étudié concerne la gestion de la consommation d'énergie dans les réseaux de télécommunication en utilisant un protocole de routage multi-chemins pour minimiser la capacité des liens utilisée. Nous proposons un modèle d'optimisation bi-niveaux dans lequel le premier niveau représente la fonction de gestion de l'énergie et le deuxième est un protocole de routage multi-chemins. Ensuite, le problème est reformulé par des formulations PLNE en remplaçant le problème du deuxième niveau par ses conditions d'optimalité. Ces formulations sont utilisées pour résoudre le problème avec les algorithmes classiques de plans coupants et de branch-and-cut. Les expérimentations sont effectuées sur des instances réelles afin de comparer les algorithmes proposés et d'évaluer l'efficacité de notre modèle par rapport aux modèles existants à un seul chemin et de multi-objectifs.Enfin, nous étudions le problème de la maximisation d’influence dans les réseaux sociaux signés. A notre connaissance, c'est la première fois que ce problème est considéré comme un problème de programmation à deux niveaux. Nous reformulons le problème en modèles PLNE à un niveau en utilisant trois différentes conditions d'optimalité du problème de plus court chemin apparaissant dans le deuxième niveau. Ces formulations sont renforcées en ajoutant un ensemble d'inégalités valides. Des tests numériques sont effectués sur des instances aléatoires pour comparer les différentes formulations proposées. Enfin, des solutions optimales en temps polynomial sont proposées pour des cas particuliers des graphes.

This thesis addresses a class of bi-level network design problems. We are interested in investigating applications from different domains and in developing exact algorithms to solve the corresponding bi-level network problem. In particular, we study a bi-level network design problem where the leader selects a part of the network to be activated, then, in the second level, the solution must be optimal for a network flow problem in the selected sub-network. In this thesis, three applications of this problem are studied: hazmats transportation, telecommunication, and social networks analysis. The second level problem in the first and the last applications is a shortest path problem while a minimum cost flow is required in the second application.The first studied problem is the fixed charge network design problem with shortest path constraints, which is modeled as a bi-level program and can be applied in hazardous transportation. For this problem, we propose two new binary integer programming (BILP) formulations inspired by path and cycle inequalities. We incorporate these formulations in a branch-and-cut algorithm and another cutting-plane based method. Numerical experiments are performed on real instances, and random data sets generated with different criteria to examine the difficulty of the instances. The results show that the proposed cutting plane algorithms can solve up to 19% more instances than the compact formulations.The second studied problem is the energy-aware traffic engineering while using multi-path routing to minimize link capacity utilization in ISP backbone networks. We propose a bi-level optimization model where the upper level represents the energy management function, and the lower one refers to the deployed multi-path routing protocol. Then, we reformulate it as a one-level MILP replacing the second level problem by different sets of flow optimality conditions. We further use these formulations to solve the problem with classical cutting plane and branch-and-cut algorithms. The computational experiments are performed on real instances to compare the proposed algorithms and to evaluate the efficiency of our model against existing single-path and multi-objective models.Finally, we study the problem of maximization influence in signed social networks. To the best of our knowledge, it is the first time that this problem is modeled as a bi-level programming problem. We reformulate the problem as one-level MILP models using three different optimality conditions of the shortest path problem appearing in the second level. These formulations are strengthened by adding a set of valid inequalities. Computational experiments are performed using random instances to compare the different proposed formulations. Finally, explicit solutions and bounds are proposed for particular cases of instances.; Cette thèse s'adresse à la classe des problèmes de conception de réseaux bi-niveaux. Nous nous sommes intéressés à l'étude des applications des différents domaines et au développement d'algorithmes exacts pour la résolution des problème de réseaux bi-niveau correspondants. En particulier, nous avons étudié le problème de conception de réseau bi-niveau dans lequel le ``leader" sélectionne une partie du réseau à activer, puis, dans le deuxième niveau, la solution doit être optimale pour un problème de flot dans le sous-réseau sélectionné. Dans cette thèse, trois applications de ce problème sont étudiées : le transport de matières dangereuses, les réseaux de télécommunication et les réseaux sociaux. Le problème de deuxième niveau dans la première et la dernière application est un problème de plus court chemin alors qu'un flot de coûts minimum est requis dans la deuxième application.Le premier problème étudié est le problème de conception de réseau avec coût fixe avec contraintes de plus court chemin. Le problème est modélisé comme un programme bi-niveaux qui peut être appliqué dans le transport des matières dangereuses. Pour ce problème, nous proposons deux nouvelles formulations de programmation en nombres entiers (PLNE) inspirées par des inégalités de chemin et de cycle. Nous incorporons ces formulations dans des algorithmes de branch-and-cut et de plans coupants. Des tests numériques sont effectués sur des instances réelles et sur un ensembles d'instances aléatoires qui sont générées avec différents critères pour examiner la difficulté de ces instances. Les résultats montrent que les algorithmes de plan coupants proposés peuvent résoudre jusqu’à 19% d’instances de plus que les formulations compactes.Le deuxième problème étudié concerne la gestion de la consommation d'énergie dans les réseaux de télécommunication en utilisant un protocole de routage multi-chemins pour minimiser la capacité des liens utilisée. Nous proposons un modèle d'optimisation bi-niveaux dans lequel le premier niveau représente la fonction de gestion de l'énergie et le deuxième est un protocole de routage multi-chemins. Ensuite, le problème est reformulé par des formulations PLNE en remplaçant le problème du deuxième niveau par ses conditions d'optimalité. Ces formulations sont utilisées pour résoudre le problème avec les algorithmes classiques de plans coupants et de branch-and-cut. Les expérimentations sont effectuées sur des instances réelles afin de comparer les algorithmes proposés et d'évaluer l'efficacité de notre modèle par rapport aux modèles existants à un seul chemin et de multi-objectifs.Enfin, nous étudions le problème de la maximisation d’influence dans les réseaux sociaux signés. A notre connaissance, c'est la première fois que ce problème est considéré comme un problème de programmation à deux niveaux. Nous reformulons le problème en modèles PLNE à un niveau en utilisant trois différentes conditions d'optimalité du problème de plus court chemin apparaissant dans le deuxième niveau. Ces formulations sont renforcées en ajoutant un ensemble d'inégalités valides. Des tests numériques sont effectués sur des instances aléatoires pour comparer les différentes formulations proposées. Enfin, des solutions optimales en temps polynomial sont proposées pour des cas particuliers des graphes.

Combinatorial Optimization (CO) is an area of research that is in a constant progress. Solving a Combinatorial Optimization Problem (COP) consists essentially in finding the best solution (s) in a set of feasible solutions called a search space that is usually exponential in cardinality in the size of the problem. To solve COPs, several methods have been proposed in the literature. A distinction is made mainly between exact methods and approximation methods. Since it is not possible to aim for an exact resolution of NP-Complete problems when the size of the problem exceeds a certain threshold, researchers have increasingly used Hybrid (HA) or parallel computing algorithms in recent decades. In this thesis we consider the COP class of Survivability Network Design Problems. We present an approximation parallel hybrid algorithm based on a greedy algorithm, a Lagrangian relaxation algorithm and a genetic algorithm which produces both lower and upper bounds for flow-based formulations. In order to validate the proposed approach, a series of experiments is carried out on several applications: the k-Edge-Connected Hop-Constrained Network Design Problem (kHNDP) when L = 2,3, The problem of the Steiner k-Edge-Connected Network Design Problem (SkESNDP) and then, two more general problems namely the kHNDP when L >= 2 and the k-Edge-Connected Network Design Problem (kESNDP). The experimental study of the parallelisation is presented after that. In the last part of this work, we present a two parallel exact algorithms: a distributed Branch-and-Bound and a distributed Branch-and-Cut. A series of experiments has been made on a cluster of 128 processors and interesting speedups has been reached in kHNDP resolution when k=3 and L=3.; L’Optimisation Combinatoire (OC) est un domaine de recherche qui est en perpétuel changement. Résoudre un problème d’optimisation combinatoire (POC) consiste essentiellement à trouver la ou les meilleures solutions dans un ensemble des solutions réalisables appelé espace de recherche qui est généralement de cardinalité exponentielle en la taille du problème. Pour résoudre des POC, plusieurs méthodes ont été proposées dans la littérature. On distingue principalement les méthodes exactes et les méthodes d’approximation. Ne pouvant pas viser une résolution exacte de problèmes NP-Complets lorsque la taille du problème dépasse une certain seuil, les chercheurs on eu de plus en plus recours, depuis quelques décennies, aux algorithmes dits hybrides (AH) ou encore à au calcul parallèle. Dans cette thèse, nous considérons la classe POC des problèmes de conception d'un réseau fiable. Nous présentons un algorithme hybride parallèle d'approximation basé sur un algorithme glouton, un algorithme de relaxation Lagrangienne et un algorithme génétique, qui produit des bornes inférieure et supérieure pour les formulations à base de flows. Afin de valider l'approche proposée, une série d'expérimentations est menée sur plusieurs applications: le Problème de conception d'un réseau k-arête-connexe avec contrainte de borne (kHNDP) avec L=2,3, le problème de conception d'un réseau fiable Steiner k-arête-connexe (SkESNDP) et ensuite deux problèmes plus généraux, à savoir le kHNDP avec L >= 2 et le problème de conception d'un réseau fiable k-arête-connexe (kESNDP). L'étude expérimentale de la parallélisation est présentée après cela. Dans la dernière partie de ce travail, nous présentons deux algorithmes parallèles exactes: un Branch-and-Bound distribué et un Branch-and-Cut distribué. Une série d'expérimentation a été menée sur une grappe de 128 processeurs, et des accélération intéressantes ont été atteintes pour la résolution du problèmes kHNDP avec k=3 et L=3.

Combinatorial Optimization (CO) is an area of research that is in a constant progress. Solving a Combinatorial Optimization Problem (COP) consists essentially in finding the best solution (s) in a set of feasible solutions called a search space that is usually exponential in cardinality in the size of the problem. To solve COPs, several methods have been proposed in the literature. A distinction is made mainly between exact methods and approximation methods. Since it is not possible to aim for an exact resolution of NP-Complete problems when the size of the problem exceeds a certain threshold, researchers have increasingly used Hybrid (HA) or parallel computing algorithms in recent decades. In this thesis we consider the COP class of Survivability Network Design Problems. We present an approximation parallel hybrid algorithm based on a greedy algorithm, a Lagrangian relaxation algorithm and a genetic algorithm which produces both lower and upper bounds for flow-based formulations. In order to validate the proposed approach, a series of experiments is carried out on several applications: the k-Edge-Connected Hop-Constrained Network Design Problem (kHNDP) when L = 2,3, The problem of the Steiner k-Edge-Connected Network Design Problem (SkESNDP) and then, two more general problems namely the kHNDP when L >= 2 and the k-Edge-Connected Network Design Problem (kESNDP). The experimental study of the parallelisation is presented after that. In the last part of this work, we present a two parallel exact algorithms: a distributed Branch-and-Bound and a distributed Branch-and-Cut. A series of experiments has been made on a cluster of 128 processors and interesting speedups has been reached in kHNDP resolution when k=3 and L=3.; L’Optimisation Combinatoire (OC) est un domaine de recherche qui est en perpétuel changement. Résoudre un problème d’optimisation combinatoire (POC) consiste essentiellement à trouver la ou les meilleures solutions dans un ensemble des solutions réalisables appelé espace de recherche qui est généralement de cardinalité exponentielle en la taille du problème. Pour résoudre des POC, plusieurs méthodes ont été proposées dans la littérature. On distingue principalement les méthodes exactes et les méthodes d’approximation. Ne pouvant pas viser une résolution exacte de problèmes NP-Complets lorsque la taille du problème dépasse une certain seuil, les chercheurs on eu de plus en plus recours, depuis quelques décennies, aux algorithmes dits hybrides (AH) ou encore à au calcul parallèle. Dans cette thèse, nous considérons la classe POC des problèmes de conception d'un réseau fiable. Nous présentons un algorithme hybride parallèle d'approximation basé sur un algorithme glouton, un algorithme de relaxation Lagrangienne et un algorithme génétique, qui produit des bornes inférieure et supérieure pour les formulations à base de flows. Afin de valider l'approche proposée, une série d'expérimentations est menée sur plusieurs applications: le Problème de conception d'un réseau k-arête-connexe avec contrainte de borne (kHNDP) avec L=2,3, le problème de conception d'un réseau fiable Steiner k-arête-connexe (SkESNDP) et ensuite deux problèmes plus généraux, à savoir le kHNDP avec L >= 2 et le problème de conception d'un réseau fiable k-arête-connexe (kESNDP). L'étude expérimentale de la parallélisation est présentée après cela. Dans la dernière partie de ce travail, nous présentons deux algorithmes parallèles exactes: un Branch-and-Bound distribué et un Branch-and-Cut distribué. Une série d'expérimentation a été menée sur une grappe de 128 processeurs, et des accélération intéressantes ont été atteintes pour la résolution du problèmes kHNDP avec k=3 et L=3.

Given a weighted undirected graph and an integer k, the k-node-connected subgraph problem is to find a minimum weight subgraph which contains k-node-disjoint paths between every pair of nodes. We introduce new classes of valid inequalities and discuss their facial aspect. We also devise separation routines, investigate the structural properties of the linear relaxation and discuss some reduction operations that can be used in a preprocessing phase for the separation. Using these results, we devise a Branch-and-Cut algorithm and present some computational results. Then we present a new extended formulation for the the k-node-connected subgraph problem, along with a Branch-and-Cut-and-Price algorithm for solving the problem.Next, we investigate the hop-constrained version of the problem. The k node-disjoint hop-constrained network design problem is to find a minimum weight subgraph such that between every origin and destination there exist at least k node-disjoint paths of length at most L. We propose an integer linear programming formulation for L=2,3 and investigate the associated polytope. We introduce valid inequalities and devise separation algorithms. Then, we propose a B\&C algorithm for solving the problem along with some computational results.; Dans un graphe non orienté, le problème du sous-graphe k-sommet connexe consiste à déterminer un sous-graphe de poids minimum tel que entre chaque paires de sommets, il existe k chemins sommet-disjoints. Ce modèle a été étudié dans la littérature en termes d'arête connexité. Cependant, le cas de la sommet connexité n'a pas été traité jusqu'à présent. Nous décrivons de nouvelles inégalités valides et nous présentons un algorithme de Coupes et Branchements ainsi qu'une large étude expérimentale qui montrent l'efficacité des contraintes utilisées. Nous proposons ensuite une formulation étendue pour le même problème pour une connexité k=2, suivi d'un algorithme de Génération de Colonnes et Branchements pour résoudre cette formulation.Nous étudions ensuite la version avec chemins bornés du problème. Le problème consiste à trouver un sous-graphe de poids minimum, tel que entre chaque paire d'origine-destination, il existe k chemins sommet-disjoints de longueur au plus L. Nous proposons une formulation linéaire en nombres entiers pour L=2,3. Nous présentons de nouvelles inégalités valides et nous proposons des algorithmes de séparation pour ces contraintes. Nous présentons ensuite un algorithme de Coupes et Branchements qu'on a testé sur des instances de la TSPLIB.

Given a weighted undirected graph and an integer k, the k-node-connected subgraph problem is to find a minimum weight subgraph which contains k-node-disjoint paths between every pair of nodes. We introduce new classes of valid inequalities and discuss their facial aspect. We also devise separation routines, investigate the structural properties of the linear relaxation and discuss some reduction operations that can be used in a preprocessing phase for the separation. Using these results, we devise a Branch-and-Cut algorithm and present some computational results. Then we present a new extended formulation for the the k-node-connected subgraph problem, along with a Branch-and-Cut-and-Price algorithm for solving the problem.Next, we investigate the hop-constrained version of the problem. The k node-disjoint hop-constrained network design problem is to find a minimum weight subgraph such that between every origin and destination there exist at least k node-disjoint paths of length at most L. We propose an integer linear programming formulation for L=2,3 and investigate the associated polytope. We introduce valid inequalities and devise separation algorithms. Then, we propose a B\&C algorithm for solving the problem along with some computational results.; Dans un graphe non orienté, le problème du sous-graphe k-sommet connexe consiste à déterminer un sous-graphe de poids minimum tel que entre chaque paires de sommets, il existe k chemins sommet-disjoints. Ce modèle a été étudié dans la littérature en termes d'arête connexité. Cependant, le cas de la sommet connexité n'a pas été traité jusqu'à présent. Nous décrivons de nouvelles inégalités valides et nous présentons un algorithme de Coupes et Branchements ainsi qu'une large étude expérimentale qui montrent l'efficacité des contraintes utilisées. Nous proposons ensuite une formulation étendue pour le même problème pour une connexité k=2, suivi d'un algorithme de Génération de Colonnes et Branchements pour résoudre cette formulation.Nous étudions ensuite la version avec chemins bornés du problème. Le problème consiste à trouver un sous-graphe de poids minimum, tel que entre chaque paire d'origine-destination, il existe k chemins sommet-disjoints de longueur au plus L. Nous proposons une formulation linéaire en nombres entiers pour L=2,3. Nous présentons de nouvelles inégalités valides et nous proposons des algorithmes de séparation pour ces contraintes. Nous présentons ensuite un algorithme de Coupes et Branchements qu'on a testé sur des instances de la TSPLIB.

With the exponential growth of traffic driven by video and Internet services, WDM systems evolve regularly to increase optical fiber capacity. To meet the relentless need for capacity, advanced features have been integrated into optical layer leading to the notion of channel flexibility (datarate elasticity, flex-grid). In contrast, with the potential benefits that optical channel flexibility provides, network dimensioning gets even more complicated, and traditional dimensioning tools should be rethought. Moreover, some strategic and technological problems appear with optical layer flexibility. Almost, all legacy equipment in the optical layer needs to be replaced by greenfield and well-adapted equipment, which requires new investments. Furthermore, spectrum fragmentation has been identified as the main disadvantage of optical layer flexibility. This work proposes and implements different mathematical multilayer tools for network dimensioning with the aim of evaluating optical layer flexibility. It identifies profitable and advantageous use cases and networking scenarios that bring forward the interest of flex-grid and elasticity. This work also deals with the potential troubles of flexibility and provides solutions to them. Specifically, we thoroughly investigate spectrum fragmentation in operator network context, and propose some traffic engineering strategies. We propose and evaluate a new use case that combines datarate elasticity and optical restoration within a multilayer context. Finally, we state a new drawback of flex-grid technology regarding the use of legacy optical amplifiers with flex-grid networks and provide a solution to overcome this problem, Avec la croissance exponentielle du trafic lié au développement de la vidéo et des services d’Internet, les systèmes WDM évoluent régulièrement pour augmenter la capacité de la fibre optique. Pour atteindre cet objectif, les concepts d’«élasticité» et de grille WDM flexible ont été introduits et ont conduit au développement de nouveaux équipements optiques. Dans le cadre des réseaux flexibles, le dimensionnement de réseaux se complexifie, et les outils de dimensionnement traditionnels doivent être repensés. De plus, des problèmes stratégiques et technologiques apparaissent avec l’arrivée de ce nouveau concept. Presque tous les équipements optiques doivent être remplacés par d’autres mieux adaptés, entraînant un coût de déploiement additionnel. Ce travail propose et implémente des nouveaux outils mathématiques et logiciels de dimensionnement multicouche des réseaux optiques flexibles. Des cas d’usage intéressants à étudier dans le cadre des réseaux flexibles sont aussi identifiés et proposés dans cette thèse. De même, ce travail traite les problèmes principaux émanant de la flexibilité optique. De façon plus spécifique, nous étudions le problème de la fragmentation du spectre WDM flexible dans les réseaux d’opérateurs et proposons des solutions. De plus, nous proposons et évaluons un cas d’usage qui combine l’élasticité et la restauration optique du trafic dans un contexte multicouche. Enfin, nous identifions et proposons une solution au problème lié à l’utilisation des amplificateurs optiques dans les réseaux flexibles

The main objective of this thesis is to find good quality solutions for rep- resentative instances of the problem of designing a resilient and low cost IP/MPLS network, to be deployed over an existing optical transport network. This research is motivated by two complementary real-world application cases, which comprise the most important commercial and academic networks of Uruguay.To achieve this goal, we performed an exhaustive analysis of existing models and technologies. From all of them we took elements that were contrasted with the par- ticular requirements of our counterparts. We highlight among these requirements, the need of getting solutions transparently implementable over a heterogeneous net- work environment, which limit us to use widely standardized features of related technologies. We decided to create new models more suitable to fit these needs.These models are intrinsically hard to solve (NP-Hard). Thus we developed meta- heuristics to find solutions to these real-world instances. Evolutionary Algorithms and Greedy Randomized Adaptive Search Procedures obtained the best results.As it usually happens, prospective real-world problems are surrounded by uncer- tainty. Therefore, we have worked closely with our counterparts to reduce the fuzzi- ness upon data to a set of representative cases. They were combined with different strategies of design to get to scenarios, which were translated into representative instances of these problems.Finally, the algorithms were fed with this information, and from their outcome we derived our results and conclusions.; L'objectif principal de cette thèse est de trouver des solutions de bonne qualité à des instances représentatives du problème de la conception d'un réseau IP/MPLS qui soit résistant et de faible coût, déployé sur une infrastructure de transport optique existante. Ces travaux ont été motivés par deux cas réels, concernant les plus grands réseaux commercial et académique d'Uruguay. Ce type de problème étant NP difficile, nous avons développé des méta-heuristiques pour trouver des solutions, basées dans les méthodologies GRASP et GA, combinées avec une analyse détaillée des incertitudes associées avec les problèmes. Ces travaux ont ainsi permis de traiter efficacement les deux familles de problèmes réels de grande taille.

International audience; Nous nous intéressons dans ce papier au problème de dimensionnement d'un réseau optique multicouche, utilisant la technologie OFDM (Orthogonal Frequency Division Multiplexing) Multi-Bandes. Etant donnée une couche physique de réseau composée d'un ensemble de noeuds de transmission, liés par des fibres optiques, et des demandes définies par une origine, une destination et une quantité de trafic. On dispose d'un ensemble de capacités modulaires, appelées sous-bandes OFDM, à installer entre les nœuds de transmission, de sorte que la circulation du trafic soit possible. Chaque sous-bande possède une capacité et induit un coût d'installation, qui est celui des équipements optiques qui génèrent la sous-bande. Si une ou plusieurs sous-bandes sont installées entre deux noeuds de transmission, on dit qu'il existe un lien virtuel entre ces noeuds. L'ensemble des liens virtuels ainsi que les noeuds extrémités définissent la couche virtuelle du réseau optique. Le problème que nous étudions peut alors être défini comme suit. Nous souhaitons déterminer le nombre de sous-bandes OFDM à installer sur les liens du réseau, de sorte que toute les demandes soient routées, que chaque sous-bande utilisée soit associée à un chemin utilisant des fibres optiques, et que le coût total soit minimum. Nous appellerons ce problème Conception de Réseau Optique Multi-Bandes (Optical Multi-Band Network Design (OMBND) problem). Nous proposons ici une approche de modélisation basée sur des coupes, et donnons une formulation en programme linéaire en nombres entiers ayant un nombre exponentiel de contraintes. Nous examinons d'abord le polyèdre associé à la formulation en coupes ainsi que la structure faciale des contraintes de base. Nous dérivons ensuite d'autres familles d'inégalités valides, et décrivons les conditions nécessaires aussi bien que les conditions suffisantes pour qu'elles définissent des facettes non triviales du polyèdre. Par ailleurs, nous proposons une étude expérimentale afin d'avoir un aperçu sur l'efficacité, en pratique, des contraintes valides introduites. Nous décrivons d'abord les procédures de séparation que nous proposons afin de générer chaque famille d'inégalités valides. Nous donnons ensuite les détails de la mise en œuvre et présentons les instances de réseaux considérées dans notre étude expérimentale. Enfin, des résultats numériques sont donnés pour des instances réalistes issues de la librairie SNDlib, ainsi que pour des instances réelles fournies par Orange Labs. Nos résultats montrent le gain apporté par les inégalités valides proposées comparé à la formulation de base. En particulier, les inégalités de type Min Set I, Capacitated Cutset inequalities et Flow-Cutset inequalities ont permis de réduire sensiblement le saut d'intégrité, et ainsi d'améliorer la qualité de la relaxation linéaire de la formulation en coupes.

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Passengers, both actual and potential, have a certain idea about the accessibility (in the geographical sense of the word meaning «possibility of access») offered by an urban public transport network. The dependent factors are linked to the individual (status, usual method of transport, his urban experience,...) ; to the characteristics of the journey, real or virtual; his own perception of the transport offer as well as his perception of the area covered by the network. Planning generally takes the first two elements into account. The generalized costs of travel are calculated (journey time and value of time) or activity programmes are determined. The aim of this study is to examine those elements not normally taken into account but which affect what we label topological representation.Due to the «anisotropy» which a public transport network creates between different directions or more specifically the different routes within the space, it modifies the distance between points, thus creating a special time-space. It transforms the relative positions of places, or in other words the topology.In this way, the transport network plays on the feelings of nearness, distance and the idea of connection. It transforms both the limits of the territory an individual belongs to and the neighbouring areas.It can thus be seen using mental maps as a form of analysis, that the network influences our representation of space.Mental maps play a supporting role to an individual's transport strategy. Due to the effect of feedback, the maps have a direct or indirect influence on the structuration of even spatial networks by selective activation or decline of certain areas.The knowledge of the relationship between territorial structures and cognitive schematic description of actions using mental maps, can contribute towards enriching methods used in the planning and evaluating of transport networks.; L'intérêt pour les transports collectifs ne cesse de croître avec la prise de conscience des problèmes engendrés par le «tout automobile». Dans ce contexte, les transports en commun en site propre, et particulièrement les tramways, reconquièrent les villes. Toutes ces nouvelles orientations représentent des sommes d'argent considérables, c'est pourquoi les questions de conception et d'évaluation des projets de transport public sont cruciaux.Cette thèse développe une méthode qualitative d'aide à la conception et à l'évaluation des réseaux de transports collectifs et s'intéresse, plus spécifiquement aux lignes de tramway. La méthode constitue aussi un outil puissant de pondération des outils quantitatifs.Toute personne possède une représentation mentale de l'espace urbain qu'elle parcourt réellement ou virtuellement. Les réseaux de transport collectif influencent les cartes mentales de l'espace urbain. Ils contraignent la perception que les gens ont de la ville à travers leurs itinéraires mais aussi modifient les distances entre les points, créant un espace temps spécifique. Cependant, les cartes mentales, tels des instruments de navigation, agissent par activations sélectives ou abandon de certaines branches du réseau. C'est pourquoi l'étude des représentations mentales, de leur capacité à intégrer des éléments nouveaux comme une nouvelle ligne de transport public est capitale.Cette recherche étudie les éléments constitutifs des cartes mentales puis la manière dont celles-ci évoluent avec la mise en service d'une nouvelle ligne de transport collectif. Elle s'intéresse aussi à la taille, à la localisation des territoires d'appartenance des individus et à leurs évolutions, question essentielle pour désenclaver les quartiers en difficulté.Les enseignements cernent les éléments du transport collectif qui déterminent fortement les représentations mentales. La topologie de celles-ci, les seuils de perception sont analysés en particulier et partiellement expliqués. Enfin, les cartes mentales peuvent se regrouper par types selon leur capacité à intégrer des éléments nouveaux. Chaque type correspond à un profil d'individu. Cette conclusion est capitale car elle permet, par l'utilisation de la méthode, d'évaluer dans quelle mesure les représentations mentales des individus, concernés par un projet de transport collectif, sont enclines à intégrer la future ligne ou non.Les résultats de cette recherche, ainsi que la méthode développée, sont autant d'enseignements précieux pour un aménageur ou, de manière générale, un décideur en matière d'urbanisme et de transport.