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.

In this thesis we study problems in the context of inventory control and facility location. In chapter 2 we study the competition among risk averse newsvendors. We showed that the well-known result for the single-product monopoly firm, which states higher risk aversion causes the firm to reduce its order quantity, cease to hold under the competition. We concluded that the higher risk aversion does not necessarily cause both firms to reduce their order quantity. We showed that the impact of risk aversion on equilibrium quantities is a trade-off between two effects: (a) Own risk aversion increment which causes that the firm reduces its order quantity and (b) Effect of spillover demand from competitor which causes that the firm increases its order quantity. We also show which firm raises its order quantity as both firms become more risk averse depending on their attributes: profitability ratio (overstocking to understocking ratio), initial risk aversion level and demand characteristic (distribution and substitution). In Chapter 3, we study how the operational decisions of a firm's manager depend on her own incentives, the capital structure, and financial decisions in the context of the newsvendor framework. We showed that in contrast to common practices, tying the manager's compensation to stock price (equity value) may not be optimal for shareholders. We propose to tie the managers' compensation to the firm value or include a debt-like instrument in the compensation package to mitigate the risk taking behaviour of the managers. We also show how the board of directors can modify the compensation structure based on the state of the economy and publicly available information about company's demand. In Chapter 4, we study the effect of risk attitude of decision makers on well-known location problems with uncertain demand. In addition to providing mathematical formulations for those problems, we also discussed how we can solve these problems using linearization techniques. We also shed some light on the importance of considering the volatility and correlation structure. Furthermore, we apply a Bayesian updating method, a useful tool for updating the probability distribution to incorporate the consultants' view about uncertain factors in location problems.

We consider a hierarchical maximal covering location problem to locate p health centers and q hospitals in such a way that maximum demand is covered, where health centers and hospitals have successively inclusive hierarchy. Demands are 3 types: demand requiring low-level service only, demand requiring high-level service only, and demand requiring both levels of service at the same time. All types of requirements of a demand point should be either covered by hospital providing both levels of service or referred to hospital via health center since a demand point is not covered unless all levels of requirements are satisfied. Thus, a health center cannot be opened unless it is suitable to refer its covered demand to a hospital. Referral is defined as coverage of health centers by hospitals. We also added partial coverage to this complex hierarchic structure, that is, a demand point is fully covered up to the minimum critical distance, non-covered after the maximum critical distance and covered with a decreasing quality while increasing distance to the facility between minimum and maximum critical distances. We developed an MIP formulation to solve the Hierarchical Maximal Covering Location Problem with referral in the presence of partial coverage. We solved small-size problems optimally using GAMS. For large-size problems we developed a Genetic Algorithm that gives near-optimal results quickly. We tested our Genetic Algorithm on randomly generated problems of sizes up to 1000 nodes.

In this study, a bi-objective capacitated facility location problem is presented which includes partial coverage concept and relocation of facility nodes. In partial coverage, a predefined distance between a demand node and a facility node is assumed to be fully covered. After the predefined distance, the service level commences to decay linearly. The problem is designed to consider the existence of already functioning facility nodes. It is allowed to close these existing facilities and open new facilities in potential sites. However, existing facility nodes are strongly favored against new facility nodes. The objectives are the maximization of the weighted total coverage and the minimization of number of facility nodes. A novel interactive multi-objective evolutionary algorithm is proposed to solve this problem, I-TREA. I-TREA is originated from NSGA-II and designed for interactive methods benefiting from quality infeasible solutions. The performance of I-TREA is benchmarked with a modified version of NSGA-II on randomly generated problems with various sizes and utility functions.

In this thesis we study problems in the context of inventory control and facility location. In chapter 2 we study the competition among risk averse newsvendors. We showed that the well-known result for the single-product monopoly firm, which states higher risk aversion causes the firm to reduce its order quantity, cease to hold under the competition. We concluded that the higher risk aversion does not necessarily cause both firms to reduce their order quantity. We showed that the impact of risk aversion on equilibrium quantities is a trade-off between two effects: (a) Own risk aversion increment which causes that the firm reduces its order quantity and (b) Effect of spillover demand from competitor which causes that the firm increases its order quantity. We also show which firm raises its order quantity as both firms become more risk averse depending on their attributes: profitability ratio (overstocking to understocking ratio), initial risk aversion level and demand characteristic (distribution and substitution). In Chapter 3, we study how the operational decisions of a firm's manager depend on her own incentives, the capital structure, and financial decisions in the context of the newsvendor framework. We showed that in contrast to common practices, tying the manager's compensation to stock price (equity value) may not be optimal for shareholders. We propose to tie the managers' compensation to the firm value or include a debt-like instrument in the compensation package to mitigate the risk taking behaviour of the managers. We also show how the board of directors can modify the compensation structure based on the state of the economy and publicly available information about company's demand. In Chapter 4, we study the effect of risk attitude of decision makers on well-known location problems with uncertain demand. In addition to providing mathematical formulations for those problems, we also discussed how we can solve these problems using linearization techniques. We also shed some light on the importance of considering the volatility and correlation structure. Furthermore, we apply a Bayesian updating method, a useful tool for updating the probability distribution to incorporate the consultants' view about uncertain factors in location problems.

This thesis covers three main issues in content delivery with a focus on placement algorithms of replica servers and replica contents. In a content delivery system, the location of replicas is very important as perceived by a quotation: Closer is better. However, considering the costs incurred by replication, it is a challenge to deploy replicas in a cost-effective manner. The objective of our work is to optimally select the location of replicas which includes sites for replica server deployment, servers for replica contents hosting, and en-route caches for object caching. Our solutions for corresponding applications are presented in three parts of the work, which makes significant contributions for designing scalable, reliable, and efficient systems for Internet content delivery. In the first part, we define the Fault-Tolerant Facility Allocation (FTFA) problem for the placement of replica servers, which relaxes the well known Fault-Tolerant Facility Location (FTFL) problem by allowing an integer (instead of binary) number of facilities per site. We show that the problem is NP-hard even for the metric version, where connection costs satisfy the triangle inequality. We propose two efficient algorithms for the metric FTFA problem with approximation factors 1.81 and 1.61 respectively, where the second algorithm is also shown to be (1.11,1.78)- and (1,2)-approximation through the proposed inverse dual fitting technique. The first bi-factor approximation result is further used to achieve a 1.52-approximation algorithm and the second one a 4-approximation algorithm for the metric Fault-Tolerant k-Facility Allocation problem, where an upper bound of facility number (i. e. k) applies. In the second part, we formulate the problem of QoS-aware content replication for parallel access in terms of combined download speed maximization, where each client has a given degree of parallel connections determined by its QoS requirement. The problem is further converted into the metric FTFL problem and we propose an approximation algorithm which is implemented in a distributed and asynchronous manner of communication. We show theoretically that the cost of our solution is no more than 2F* + RC*, where F* and C* are two components of any optimal solution while R is the maximum number of parallel connections. Numerical experiments show that the cost of our solutions is comparable (within 4% error) to the optimal solutions. In the third part, we establish mathematical formulation for the en-route web caching problem in a multi-server network that takes into account all requests (to any server) passing through the intermediate nodes on a request/response path. The problem is to cache the requested object optimally on the path so that the total system gain is maximized. We consider the unconstrained case and two QoS-constrained cases respectively, using efficient dynamic programming based methods. Simulation experiments show that our methods either yield a steady performance improvement (in the unconstrained case) or provide required QoS guarantees. / http://proxy.library.adelaide.edu.au/login?url= http://library.adelaide.edu.au/cgi-bin/Pwebrecon.cgi?BBID=1461921 / Thesis (Ph.D.) - University of Adelaide, School of Computer Science, 2009

No description available.

In this paper, a two-stage stochastic facility location problem integrated with inven- tory and recourse decisions is studied and solved. This problem is inspired by an industrial supply chain design problem of a large retail chain with slow-moving prod- ucts. Uncertainty is expressed by a discrete and finite set of scenarios. Recourse actions can be taken after the realization of random demands. Location, inventory, transportation, and recourse decisions are integrated into a mixed-integer program with an objective minimizing the expected total cost. A dual heuristic procedure is studied and embedded into the sample average approximation (SAA) method. The computation experiments demonstrate that our combined SAA with dual heuristic algorithm has a similar performance on solution quality and a much shorter compu- tational time. / Thesis / Master of Applied Science (MASc)

No description available.