Dissertation/Thesis Abstract

Network Design With Facility Location: Approximation and Exact Techniques
by Rezapour, Mohsen, Dr.Nat., Technische Universitaet Berlin (Germany), 2015, 133; 10701438
Abstract (Summary)

In this thesis, we consider a family of problems that combine network design and facility location. Such problems arise in many practical applications in different fields such as telecommunications, transportation networks, logistic, and energy supply networks. In facility location problems, we want to decide which facilities to open and how to assign clients to the open facilities so as to minimize the sum of the facility opening costs and client connection costs. These problems typically do not involve decisions concerning the routing of the clients’ demands to the open facilities; once we decided on the set of open facilities, each client is served by the closest open facility. In network design problems, on the other hand, we generally want to design and dimension a minimum-cost routing network providing sufficient capacities to route all clients’ demands to their destinations. These problems involve deciding on the routing of each client’s demand. But, in contrast to facility location problems, demands’ destinations are predetermined. In many modern day applications, however, all these decisions are interdependent and affect each other. Hence, they should be taken simultaneously. A naive strategy that first decides which facilities to open, and then builds routing networks connecting clients to the open facilities, may lead to very poor solutions. This has motivated several new combined network design facility location problems which are studied in this thesis. We develop new algorithmic techniques and solution approaches for these problems, building on the known techniques for facility location and network design. In a first line of work, we study problems that integrate buy-at-bulk network design into the classical facility location problem. More precisely, we consider generalizations of the facility location problem where multiple clients may share capacitated trees to connect to the open facilities instead of requiring direct links. The task is to open facilities (sinks) and route all client demands to the open facilities via a capacitated access network that is constructed installing access cables of different costs and capacities. On the theoretical side, we present the first LP-based approximation algorithm for this problem and prove an upper bound of O(K) on the Integrality gap of the underlying LP. We also undertake the first computational study for this problem. To this end, we provide compact and exponential-sized formulations for the problem and develop a branch-cut-and-price algorithm allowing us to solve very large real-world instances of the problem. In many real-world applications, particularly in telecommunications, there is the additional requirement to connect the open facilities via high bandwidth core cables. In the simplest case, this leads to variants of the problem in which open facilities are connected via a tree-like core network that consists of infinite capacity cables. We analyze two fundamental versions of this problem: In the Buy-at-Bulk version of the problem, each access cable type has a fixed setup cost and a fixed capacity, whereas in the Deep-Discount problem version, each cable type has unlimited capacity but a traffic-dependent variable cost in addition to its fixed setup cost. The Buy-at-Bulk version arises in the planing of telecommunication networks, while the Deep-Discount problem version is motivated by applications in logistic and transportation networks. We develop the first constant-factor approximation algorithms for these connected versions. Using sampling techniques, we then improved the approximation factors. We were even able to prove a tighter bound of O(1) on the the Integrality gap of an LP formulation of the problem similar to one for the unconnected version. The core network plays a primary role for the service availability and the service quality in telecommunications networks. Therefore it is common to require that the core networks are fault-tolerant and have short routing paths. In the final part of this thesis we focus on the core network design. To take these requirements into account, we introduce and study another network design facility location problem where the core network has to fulfill simultaneous survivability and hop-length restrictions between the chosen facilities. It is easy to see that it is already NP-hard to compute a constant-factor approximation for the problem. Hence, we focus our research on IP based techniques. We propose two strong extended formulations for the problem and devise a practically efficient branch-and-cut algorithm based on Benders decomposition for its solution.

Indexing (document details)
Advisor: Bley, Andreas
School: Technische Universitaet Berlin (Germany)
School Location: Germany
Source: DAI-C 81/1(E), Dissertation Abstracts International
Subjects: Computer science
Keywords: Facility location problems
Publication Number: 10701438
ISBN: 9781392870198
Copyright © 2020 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy