Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Please read the abstract (Summary) in the section 00front of this document / Dissertation (MEng (Electronic Engineering))--University of Pretoria, 2007. / Electrical, Electronic and Computer Engineering / MEng / Unrestricted

No description available.

Location-allocation problems can be described generically as follows: Given the location or distribution (perhaps, probabilistic) of a set of customers and their associated demands for a given product or service, determine the optimum location of a number of service facilities and the allocation of products or services from facilities to customers, so as to minimize total (expected) location and transportation costs. This study is concerned with a particular subclass of location-allocation problems involving capacitated facilities and a continuum of demand. Specifically, two minisum, network-based location-allocation problems are analyzed in which facilities having known finite capacities are to be located so as to optimally supply/serve a known continuum of demand. The first problem considered herein, is an absolute p-median problem in which p > l capacitated facilities are to be located on a chain graph having both nodal and link demands, the latter of which are defined by nonnegative, integrable demand functions. In addition, the problem is balanced, in that it is assumed the total demand equals the total supply. An exact solution procedure is developed, wherein the optimality of a certain location-allocation scheme (for any given ordering of the facilities) is used to effect a branch and bound approach by which one can identify an optimal solution to the problem. Results from the chain graph analysis are then used to develop an algorithm with which one can solve a dynamic, sequential location-allocation problem in which a single facility per period is required to be located on the chain. Finally, an exact solution procedure is developed for locating a capacitated, absolute 2-median on a tree graph having both nodal and link demands and for which the total demand is again equal to the total supply. This procedure utilizes an algorithm to construct two subtrees, each of whose ends constitute a set of candidate optimal locations for one of the two elements of an absolute 2-median. Additional localization results are used to further reduce the number of candidate pairs (of ends) that need to be considered, and then a post-localization analysis provides efficient methods of comparing the relative costs of the remaining pairs. / Ph. D.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Not available / text

Orientadores: Edson Moschim, Felipe Rudge Barbosa / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-09T16:46:35Z (GMT). No. of bitstreams: 1 Martins_IndayaraBertoldi_M.pdf: 1239150 bytes, checksum: 785fa753532d04d698ee47a542591430 (MD5) Previous issue date: 2007 / Resumo: Neste trabalho investigamos o desempenho de redes ópticas avançadas, em particular redes de chaveamento de pacotes ópticos (Optical Packet Switching Network-OPSN), constituídos por arquiteturas com topologias em malha e nós ópticos sem armazenador. Utilizou-se distribuição de tráfego uniforme, na qual todos os nós geram a mesma quantidade de tráfego para todos os outros nós. Foram avaliados vários parâmetros de redes OPSN, principalmente número médio de saltos e capacidade efetiva da rede, bem como comparações entre topologias anel e malha, considerando como parâmetros principais vazão e desempenho, e os impactos causados por falhas de enlaces. Demonstrouse também que o aumento do número de nós em OPSNs, não necessariamente aumenta o desempenho ou capacidade / Abstract: In this work we have investigated the performance of advanced optical networks, more specifically optical packet switched networks (OPSN), with architectures comprising fully connected mesh topologies and optical bufferless nodes. We have adopted uniform traffic distribution, in which all nodes generate the same traffic to every other node. Several parameters of the OPSNs have been evaluated, mainly average number of hops and effective network capacity, as well as comparisons between the ring and mesh network topologies, considering as main parameters the network throughput and performance, and the impacts caused by failures of links. We demonstrate that increasing the number of nodes in OSPNs does not necessarily increase performance or capacity / Mestrado / Telecomunicações e Telemática / Mestre em Engenharia Elétrica

by Arjang A. Assad. / Includes bibliographical references. / Supported in part by the U.S. Department of Transportation, Transportation Advanced Research Program (TARP) DOT-TSC-1058

In this thesis we develop integer programming approaches for solving network flow problems with equal-split restrictions. Such problems arise in traffic engineering of internet protocol networks. Equal-split structure is used in protocols like OSPF and IS-IS that allow flow to be split among the multiple shortest paths. Equal-split assumptions also arise in peer-to-peer networks and road optimization problems. All the previous work on this problem has been focused on developing heuristic methods for the specific applications. We are the first ones to study the problem as a general network flow problem and provide a polyhedral study. First we consider a general multi-commodity network flow problem with equal split restrictions. This problem is NP-hard in general. We perform a polyhedral study on mixed integer linear programming formulation for this problem. Valid inequalities are obtained, and are incorporated within a branch-and-cut framework to solve the problem. We provide fast separation schemes for most of the families of valid inequalities. Computational results are presented to show the effectiveness of cutting plane families. Next, we consider the OSPF weight setting problem. We propose an integer programming formulation for this problem. A decomposition based approach to solve the problem is presented next. Valid inequalities, exploiting the structure, are obtained for this problem. We also propose heuristic methods to get good starting solutions for the problem. The proposed cutting planes and heuristic methods are integrated within a branch-and-cut framework to solve the problem. We present computational experiments that demonstrate the effectiveness of our approach to obtain solutions with tight optimality gaps as compared with default CPLEX. Finally, we consider an equal split flow problem on bipartite graphs. We present an integer programming formulation for this problem that models the equal-split in a different way than the multi-commodity network flow problem discussed before. Valid inequalities and heuristic methods for this problem are proposed, and are integrated within the branch-and-cut framework. We present computational experiments demonstrating the effectiveness of our solution strategy. We present an alternate formulation for the problem with some favorable polyhedral properties. Lastly, a computational comparison between the two formulations is presented.

Graphs are a fundamental and widely-used abstraction for representing data. We can analytically study interesting aspects of real-world complex systems such as the Internet, social systems, transportation networks, and biological interaction data by modeling them as graphs. Graph-theoretic and combinatorial problems are also pervasive in scientific computing and engineering applications. In this dissertation, we address the problem of analyzing large-scale complex networks that represent interactions between hundreds of thousands to billions of entities. We present SNAP, a new high-performance computational framework for efficiently processing graph-theoretic queries on massive datasets. Graph analysis is computationally very different from traditional scientific computing, and solving massive graph-theoretic problems on current high performance computing systems is challenging due to several reasons. First, real-world graphs are often characterized by a low diameter and unbalanced degree distributions, and are difficult to partition on parallel systems. Second, parallel algorithms for solving graph-theoretic problems are typically memory intensive, and the memory accesses are fine-grained and highly irregular. The primary contributions of this dissertation are the design and implementation of novel parallel graph algorithms for traversal, shortest paths, and centrality computations, optimized for the small-world network topology, and high-performance multithreaded architectures and multicore servers. SNAP (Small-world Network Analysis and Partitioning) is a modular, open-source framework for the exploratory analysis and partitioning of large-scale networks. With SNAP, we demonstrate the capability to process massive graphs with billions of vertices and edges, and achieve up to two orders of magnitude speedup over state-of-the-art network analysis approaches. We also design a new parallel computing benchmark for characterizing the performance of graph-theoretic problems on high-end systems; study data representations for dynamic graph problems on parallel systems; and apply algorithms in SNAP to solve real-world problems in social network analysis and systems biology.