Η δρομολόγηση και ανάθεση μηκών κύματος (routing and wavelength assignment - RWA) αποτελεί ένα πολύ σημαντικό πρόβλημα, που απασχολεί τους σχεδιαστές WDM οπτικών δικτύων και είναι γνωστό, πως είναι NP-πλήρες. Στην εργασία αυτή σχεδιάζουμε και υλοποιούμε έναν αλγόριθμο για το στατικό RWA, που βασίζεται σε έναν προτεινόμενο σχηματισμό (μη ακέραιου) γραμμικού προγραμματισμού (linear programming - LP). Ισχυριζόμαστε, πως ο σχηματισμός αυτός είναι σε θέση να παρέχει ακέραιες βέλτιστες λύσεις (παρά την εν γένει μη ακέραια φύση του) για ένα μεγάλο ποσοστό στιγμιότυπων εισόδου, οδηγώντας έτσι σε αντίστοιχες ακριβείς λύσεις του RWA. Η πολυπλοκότητα του αλγόριθμου κυριαρχείται από το χρόνο εκτέλεσης του αλγόριθμου Simplex, ο οποίος θεωρείται αποδοτικός για μια μεγάλη πλειοψηφία στιγμιότυπων εισόδου. Στα διαφανή (πλήρως οπτικά) δίκτυα, η ποιότητα του σήματος υπόκειται σε μια ποικιλία από φυσικές εξασθενήσεις, όπως είναι η διασπορά λειτουργίας πόλωσης (polarization mode dispersion - PMD), ο θόρυβος αυθόρμητης εκπομπής ενισχυτή (amplified spontaneous emission - ASE - noise) και η χρωματική διασπορά (chromatic dispersion - CD). Αυτές οι εξασθενήσεις μοντελοποιούνται γραμμικά και μπορούν να αντιμετωπιστούν αποτελεσματικά από ένα σύνολο αναλυτικών τύπων ως επιπρόσθετοι περιορισμοί στο RWA. Εφαρμόζουμε τον αλγόριθμό μας και εκτελούμε RWA βασισμένο σε περιορισμούς εξασθένησης, με σκοπό να παρατηρήσουμε συγκριτικά αποτελέσματα στην απόδοση ενός τυπικού μητροπολιτικού δικτύου υπό διάφορες παραμέτρους του δικτύου και των εξασθενήσεων, όπως είναι ο ρυθμός bit, ο τύπος και το κέρδος των ενισχυτών, η χρησιμοποιούμενη διάταξη διαμόρφωσης, κλπ. / Routing and wavelength assignment (RWA) is a very important problem concerning WDM optical network designers and is known to be NP-complete. In this work, we design and implement an algorithm for the static RWA, that is based on a proposed (not integer) linear programming formulation. We claim, that this formulation is able to provide integer optimal solutions (despite its non integral nature) for a large fraction of input instances, yielding thus to corresponding exact RWA solutions. The algorithm's complexity is dominated by the execution time of Simplex LP-solver, that is considered efficient in the great majority of all possible input instances. In transparent (all-optical) networks, the signal quality is subject to a variety of physical impairments, such as polarization mode dispersion (PMD), amplified spontaneous emission (ASE) noise and chromatic dispersion (CD). Those impairments are linearly modeled and are handled effectively by a set of analytical formulae as additional constraints on RWA. We apply our algorithm to perform impairment-constraint based RWA, in order to obtain comparative results of a typical metropolitan network's performance under various network and impairment parameters, such as bit rate, amplifier gain and type, modulation format used, etc.

De nombreux problèmes en transport et en logistique peuvent être formulés comme des modèles de conception de réseau. Ils requièrent généralement de transporter des produits, des passagers ou encore des données dans un réseau afin de satisfaire une certaine demande tout en minimisant les coûts. Dans ce mémoire, nous nous intéressons au problème de conception de réseau avec coûts fixes et capacités. Ce problème consiste à ouvrir un sous-ensemble des liens dans un réseau afin de satisfaire la demande, tout en respectant les contraintes de capacités sur les liens. L'objectif est de minimiser les coûts fixes associés à l'ouverture des liens et les coûts de transport des produits. Nous présentons une méthode exacte pour résoudre ce problème basée sur des techniques utilisées en programmation linéaire en nombres entiers. Notre méthode est une variante de l'algorithme de branch-and-bound, appelée branch-and-price-and-cut, dans laquelle nous exploitons à la fois la génération de colonnes et de coupes pour la résolution d'instances de grande taille, en particulier, celles ayant un grand nombre de produits. En nous comparant à CPLEX, actuellement l'un des meilleurs logiciels d'optimisation mathématique, notre méthode est compétitive sur les instances de taille moyenne et supérieure sur les instances de grande taille ayant un grand nombre de produits, et ce, même si elle n'utilise qu'un seul type d'inégalités valides. / Many problems in transportation and logistics can be formulated as network design models. They usually require to transport commodities, passengers or data in a network to satisfy a certain demand while minimizing the costs. In this work, we focus on the multicommodity capacited fixed-charge network design problem which consists of opening a subset of the links in the network to satisfy the demand. Each link has a capacity and a fixed cost that is paid if it is opened. The objective is to minimize the fixed costs of the opened links and the transportation costs of the commodities. We present an exact method to solve this problem based on mixed integer programming techniques. Our method is a specialization of the branch-and-bound algorithm, called branch-and-price-and-cut, in which we use column generation and cutting-plane method to solve large-scale instances. We compare our method with CPLEX, currently one of the best solver. Numerical results show that our method is competitive on medium-scale instances and better on large-scale instances.

No description available.

Les problèmes de conception de réseaux ont reçu un intérêt particulier et ont été largement étudiés de par leurs nombreuses applications dans différents domaines, tels que les transports et les télécommunications. Nous nous intéressons dans ce mémoire au problème de conception de réseaux avec coûts d’ajout de capacité. Il s’agit d’installer un ensemble d’équipements sur un réseau en vue de satisfaire la demande, tout en respectant les contraintes de capacité, chaque arc pouvant admettre plusieurs équipements. L’objectif est de minimiser les coûts variables de transport des produits et les coûts fixes d’installation ou d’augmentation de capacité des équipements. La méthode que nous envisageons pour résoudre ce problème est basée sur les techniques utilisées en programmation linéaire en nombres entiers, notamment celles de génération de colonnes et de coupes. Ces méthodes sont introduites dans un algorithme général de branch-and-bound basé sur la relaxation linéaire. Nous avons testé notre méthode sur quatre groupes d’instances de tailles différentes, et nous l’avons comparée à CPLEX, qui constitue un des meilleurs solveurs permettant de résoudre des problèmes d’optimisation, ainsi qu’à une méthode existante dans la littérature combinant des méthodes exactes et heuristiques. Notre méthode a été plus performante que ces deux méthodes, notamment pour les instances de très grandes tailles. / Network design problems received a particular interest and have been widely studied because of their many applications in different areas, such as logistics and telecommunications. We focus in this work on the multicommodity capacitated network design problem with capacity expansion costs. It consists in opening a set of facilities on a network in order to meet the demand of some commodities, while respecting the capacity constraints. Each arc can admit several facilities. The objective is to minimize the commodities transportation costs, and the fixed costs of opening or increasing the capacity of the facilities. The method we are using to solve this problem is based on techniques used in integer programming, including column generation and cutting-plane methods. These methods are introduced into a general branch-and-bound algorithm, based on linear relaxation. We test our method on four groups of instances of different sizes, and we compare it with CPLEX, which is one of the best solvers available for optimization problems. We compare it also with an existing method in the literature, combining exact and heuristic methods. Numerical results show that our method was able to outperform both methods, especially when tested on large scale instances.

No description available.