The aim of thiswork is to locate a semi-obnoxious facility, i.e. tominimize the distances to a given set of customers in order to save transportation costs on the one hand and to avoid undesirable interactions with other facilities within the region by maximizing the distances to the corresponding facilities on the other hand. Hence, the goal is to satisfy economic and environmental issues simultaneously. Due to the contradicting character of these goals, we obtain a non-convex objective function. We assume that distances can be measured by rectilinear distances and exploit the structure of this norm to obtain a very efficient dual pair of algorithms.

No description available.

<div>The problem of optimally placing sensors can often be formulated as a facility location problem. In the literature of operations research, facility location problems are mathematical optimization problems where one or more facilities must be placed in relation to a given number of demand points or customers. Within the context of sensor placement, for example, this translates to placing wireless communication nodes that connect to a set of users or placing smoke detectors to adequately cover a region for safety assurances. However, while the classical facility location problem has been extensively studied, its direct applicability to and effectiveness for the optimal sensor placement problem can be diminished when real-world uncertainties are considered. In addition, the physics of the underlying systems in optimal sensor placement problems can directly impact the effectiveness of facility location formulations. Extensions to existing location formulations that are tailored for the system of interest are necessary to ensure optimal sensor network design.</div><div><br></div><div>This dissertation focuses on developing and applying problem-specific optimal sensor placement methods under uncertainty in sensor performance. With the classical discrete facility location problems as a basis, our models are formulated as mixed-integer linear and nonlinear programs that, depending on the specific application, can also be in the form of a stochastic program, a robust optimization framework, or require probability distributions for uncertain parameters. We consider optimal placement problems from three different areas, particularly the optimal placement of data concentrators in Smart Grid communications networks, the optimal placement of flame detectors within petrochemical facilities, and the optimal selection of infectious disease detection sites across a nation. For each application, we carefully consider the underlying physics of the system and the uncertainties and then develop extensions of previous sensor placement formulations that effectively handle these qualities. In addition, depending on the degree of nonlinear complexity of the problem, specific relaxations and iterative solution strategies are developed to improve the ability to find tractable solutions. All proposed models are implemented in Pyomo, a Python-based optimization modeling language, and solved with state-of-the-art optimization solvers, including IPOPT, Gurobi, and BARON for nonlinear, mixed-integer, and mixed-integer nonlinear programs, respectively. Numerical results show that our tailored formulations for the problems of interest are effective in handling uncertainties and provide valuable sensor placement design frameworks for their respective industries. Furthermore, our extensions for placement of sensors under probabilistic failure are appropriately general for application in other areas.<br><b></b><i></i><u></u><br></div>

Facility location, as an important topic in computer science and operations research, is concerned with placing facilities for "serving" demand points (each representing a customer) to minimize the (service) cost. In the real world, data is often associated with uncertainty because of measurement inaccuracy, sampling discrepancy, outdated data sources, resource limitation, etc. Hence, problems on uncertain data have attracted much attention. In this dissertation, we mainly study a classical facility location problem: the k- center problem and several of its variations, on uncertain points each of which has multiple locations that follow a probability density function (pdf). We develop efficient algorithms for solving these problems. Since these problems more or less have certain geometric flavor, computational geometry techniques are utilized to help develop the algorithms. In particular, we first study the k-center problem on uncertain points on a line, which is aimed to find k centers on the line to minimize the maximum expected distance from all uncertain points to their expected closest centers. We develop efficient algorithms for both the continuous case where the location of every uncertain point follows a continuous piecewise-uniform pdf and the discrete case where each uncertain point has multiple discrete locations each associated with a probability. The time complexities of our algorithms are nearly linear and match those for the same problem on deterministic points. Then, we consider the one-center problem (i.e., k= 1) on a tree, where each uncertain point has multiple locations in the tree and we want to compute a center in the tree to minimize the maximum expected distance from it to all uncertain points. We solve the problem in linear time by proposing a new algorithmic scheme, called the refined prune-and-search. Next, we consider the one-dimensional one-center problem of uncertain points with continuous pdfs, and the one-center problem in the plane under the rectilinear metric for uncertain points with discrete locations. We solve both problems in linear time, again by using the refined prune-and-search technique. In addition, we study the k-center problem on uncertain points in a tree. We present an efficient algorithm for the problem by proposing a new tree decomposition and developing several data structures. The tree decomposition and these data structures may be interesting in their own right. Finally, we consider the line-constrained k-center problem on deterministic points in the plane where the centers are required to be located on a given line. Several distance metrics including L1, L2, and L1 are considered. We also study the line-constrained k-median and k-means problems in the plane. These problems have been studied before. Based on geometric observations, we design new algorithms that improve the previous work. The algorithms and techniques we developed in this dissertation may and other applications as well, in particular, on solving other related problems on uncertain data.

The reliability issue of the infrastructure systems has become one of the major concerns of the system operators. This dissertation is a collection of four published and working papers that address the specific reliable design and operations problems from three different application settings: transportation/telecommunications network, distribution network, and power plant. In these four projects, key random factors like site disruption and uncertain demand are explicitly considered and proper research tools including stochastic programming, robust optimization, and variants of robust optimization are applied to formulate the problems based on which the important and challenging modelling elements (nonlinear congestion, disruption caused demand variation, etc.) can be introduced and studied. Besides, for each of the optimization models, we also develop advanced solution algorithms that can solve large-scale instances within a short amount of time and devise comprehensive numerical experiments to derive insights. The modelling techniques and solution methods can be easily extended to study reliability issues in other applications.

The exploding HD video streaming traffic calls for deploying content servers deeper inside network operators infrastructures. Telco-CDN are new content distribution services that are managed by Internet Service Providers (ISP). Since the network operator controls both the infrastructure and the content delivery overlay, it is in position to engineer Telco-CDN so that networking resources are optimally utilized. In this thesis, we focus on the optimal resource placement in Telco-CDN. We first investigated the placement of application components in Telco-CDN. Popular services like Facebook or Twitter, with a size in the order of hundreds of Terabytes, cannot be fully replicated on a single data-center. Instead, the idea is to partition the service into smaller components and to locate the components on distinct sites. It is the same and unique method for Telco-CDN operators. We addressed this k-Component Multi-Site Placement Problem from an optimization standpoint. We developed linear programming models, designed approximation and heuristic algorithms to minimize the overall service delivery cost. Thereafter, we extend our works to address the problem of optimal video place- ment for Telco-CDN. We modeled this problem as a k-Product Capacitated Facility Location Problem, which takes into account network conditions and users¿ prefer- ences. We designed a genetic algorithm in order to obtain near-optimal performances of such "push" approach, then we implemented it on the MapReduce framework in order to deal with very large data sets. The evaluation signifies that our optimal placement keeps align with cooperative LRU caching in term of storage efficiency although its impact on network infrastructure is less severe. We then explore the caching decision problem in the context of Information Cen- tric Network (ICN), which could be a revolutionary design of Telco-CDN. In ICN, routers are endowed with caching capabilities. So far, only a basic Least Recently Used (LRU) policy implemented on every router has been proposed. Our first contri- bution is the proposition of a cooperative caching protocol, which has been designed for the treatment of large video streams with on-demand access. We integrated our new protocol into the main router software (CCNx) and developed a platform that automatically deploys our augmented CCNx implementation on real machines. Ex- periments show that our cooperative caching significantly reduces the inter-domain traffic for an ISP with acceptable overhead. Finally, we aim at better understanding the behavior of caching policies other than LRU. We built an analytical model that approximates the performance of a set of policies ranging from LRU to Least Frequently Used (LFU) in any type of network topologies. We also designed a multi-policy in-network caching, where every router implements its own caching policy according to its location in the network. Compared to the single LRU policy, the multi-caching strategy considerably increases the hit- ratio of the in-network caching system in the context of Video-on-Demand application. All in one, this thesis explores different aspects related to the resource placement in Telco-CDN. The aim is to explore optimal and near-optimal performances of various approaches.

A planar single facility location problem, also known as the Fermat&ndash / Weber problem, is to

Hazardous Materials (HazMat) are transported throughout Canada in a great number of road shipments. The transportation of HazMat poses special risks for neighboring population and environment. While HazMat accidents are rare events, they could be catastrophic in nature and could result in substantial damage to nearby communities. Effective emergency response plays an important role in the safe transportation of HazMat. Transportation of HazMat involves different parties, including shippers, regulators, and surrounding communities. While the shipping party is responsible for safe delivery of HazMat shipments, it is the responsibility of local emergency service agencies to respond to accidents occurring within their jurisdictions. In this research, the emergency response to HazMat transport accidents is assumed to be delegated exclusively to specially trained and equipped HazMat teams. This research proposes a new comprehensive systematic approach to determine the best location of HazMat teams on regional bases utilizing HazMat transport risk as a location criterion. The proposed model is the first to consider emergency response roles in HazMat transport risk analysis, and was intended as an optimization tool to be used by practitioners for HazMat emergency response planning. Additionally, the proposed model can be used to assess risk implications in regards to current locations of HazMat teams in a region, and to develop effective strategies for locating HazMat teams, such as closing and/or relocating teams in the region. The model investigates how HazMat team locations can be tailored to recognize the risk of transporting HazMat and would provide a more objective set of input alternatives into the multi-criteria decision making process of regionally locating HazMat teams. The proposed model was applied to the region of southwestern Ontario in effort to illustrate its features and capabilities in the HazMat emergency response planning and decision making process. Accordingly, the model provided very useful insights while reviewing several HazMat team location strategies for the southwestern Ontario region and investigating tradeoff among different factors. This research contributes to a better understanding of emergency response roles by reducing HazMat transport risks, and will greatly benefit both researchers and practitioners in the field of HazMat transport and emergency response.

The subject of this thesis is to study approximation algorithms for some network design problems in face of uncertainty. We consider two widely studied models of handling uncertainties - Robust Optimization and Stochastic Optimization. We study a robust version of the well studied Uncapacitated Facility Location Problem (UFLP). In this version, once the set of facilities to be opened is decided, an adversary may close at most β facilities. The clients must then be assigned to the remaining open facilities. The performance of a solution is measured by the worst possible set of facilities that the adversary may close. We introduce a novel LP for the problem, and provide an LP rounding algorithm when all facilities have same opening costs. We also study the 2-stage Stochastic version of the Steiner Tree Problem. In this version, the set of terminals to be covered is not known in advance. Instead, a probability distribution over the possible sets of terminals is known. One is allowed to build a partial solution in the first stage a low cost, and when the exact scenario to be covered becomes known in the second stage, one is allowed to extend the solution by building a recourse network, albeit at higher cost. The aim is to construct a solution of low cost in expectation. We provide an LP rounding algorithm for this problem that beats the current best known LP rounding based approximation algorithm.

In this thesis, we study the dynamic facility location problem with mobile customers considering the permanent facilities. Our general aim is to locate facilities considering the movements of customers in time. The problem is studied for three objectives: P-median, P-center and MINMAX P-median. We show that dynamic facility location problem is a large instance of a static facility location problem for P-median and P-center objectives. In the problem, we represent the movements of each customer in time with a time series. Using clustering approaches, we develop a heuristic approach for the problem with P-median objective. K-means algorithm is used as a clustering algorithm and dynamic time warping is used in order to define similarities between the customer time series. Solution method is tested on several experimental settings. We obtain results, which differ at most 2% from the optimal, in small computation times. Generally, in the literature, MINMAX P-median is solved with a heuristic depending on scenarios planning (see Serra and Marianov, 1998). The heuristic finds an initial solution according to scenarios, later the initial solution is tried to be improved. We provide a bounding procedure on the solution of the problem. The bounds can be used by decision maker to judge the solution quality before proceed. The bounding procedure is also analyzed in different experimental settings.