The focus of this thesis is on the design and analysis of algorithms for basic problems in Stochastic Optimization, specifically a class of fundamental combinatorial optimization problems where there is some form of uncertainty in the input. Since many interesting optimization problems are computationally intractable (NP-Hard), we resort to designing approximation algorithms which provably output good solutions. However, a common assumption in traditional algorithms is that the exact input is known in advance. What if this is not the case? What if there is uncertainty in the input? With the growing size of input data and their typically distributed nature (e.g., cloud computing), it has become imperative for algorithms to handle varying forms of input uncertainty. Current techniques, however, are not robust enough to deal with many of these problems, thus necessitating the need for new algorithmic tools. Answering such questions, and more generally identifying the tools for solving such problems, is the focus of this thesis. The exact problems we study in this thesis are the following: (a) the Survivable Network Design problem where the collection of (source,sink) pairs is drawn randomly from a known distribution, (b) the Stochastic Knapsack problem with random sizes/rewards for jobs, (c) the Multi-Armed Bandits problem, where the individual Markov Chains make random transitions, and finally (d) the Stochastic Orienteering problem, where the random tasks/jobs are located at different vertices on a metric. We explore different techniques for solving these problems and present algorithms for all the above problems with near-optimal approximation guarantees. We also believe that the techniques are fairly general and have wider applicability than the context in which they are used in this thesis.

In this study, we consider the Turkish postal delivery system and develop an effective solution approach for the combined hub location and routing problem where the location of hub nodes are determined, the nonhub regional postal offices are allocated to the hubs, and the optimal set of routes are determined for each hub. Since the realized post-routing distances between origin-destination pairs are different from those used in the hub-location model, we develop an algorithm that finds the route-compatible hub configuration and allocation paths. The algorithm is the one that iterates between the hub-location phase and a routing phase. Our strategy consists of updating the distances used in the first phase in order to produce a solution that contains the cognition of routes. Some special structures in the routed network are also identified and used for improving the solution. Computational experience is reported.

Soft sensors are an essential component of process systems engineering schemes. While soft sensor design research is important, investigation into the relationships between soft sensors and other areas of advanced monitoring and control is crucial as well. This dissertation presents two new techniques that enhance the performance of fault detection and sensor network design by integration with soft sensor technology. In addition, a chapter is devoted to the investigation of the proper implementation of one of the most often used soft sensors. The performance advantages of these techniques are illustrated with several cases studies. First, a new approach for fault detection which involves soft sensors for process monitoring is developed. The methodology presented here deals directly with the state estimates that need to be monitored. The advantage of such an approach is that the nonlinear effect of abnormal process conditions on the state variables can be directly observed. The presented technique involves a general framework for using soft sensor design and computation of the statistics that represent normal operating conditions. Second, a method for determining the optimal placement of multiple sensors for processes described by a class of nonlinear dynamic systems is described. This approach is based upon maximizing a criterion, i.e., the determinant, applied to the empirical observability gramian in order to optimize certain properties of the process state estimates. The determinant directly accounts for redundancy of information, however, the resulting optimization problem is nontrivial to solve as it is a mixed integer nonlinear programming problem. This paper also presents a decomposition of the optimization problem such that the formulated sensor placement problem can be solved quickly and accurately on a desktop PC. Many comparative studies, often based upon simulation results, between Extended Kalman filters (EKF) and other estimation methodologies such as Moving Horizon Estimation or Unscented Kalman Filter have been published over the last few years. However, the results returned by the EKF are affected by the algorithm used for its implementation and some implementations may lead to inaccurate results. In order to address this point, this work provides a comparison of several different algorithms for implementation.

In this dissertation, we consider two specific types of problems over networks. In the first problem, we explore systematic methods to address some of the challenges in largescale maintenance planning in integrated chemical sites. In the second problem, we investigate different optimization model formulations for the design of flow distribution networks where the flow is potential-driven and nonlinearly related to the potential loss. Maintenance turnaround in the processing industry is a complex asset renewal project that includes huge capital expenditures and downtime losses. The option of deferring or rescheduling a turnaround project typically provides immediate financial relief from capital expenditure. However, the risk of running into site-wide disruptions in the form of unplanned events, yield, and reliability losses is not straightforward to assess. We propose mathematical optimization models to evaluate the risk of loss from turnaround deferrals in integrated sites and provide alternatives to reliably operate the site in a medium-term horizon. In the first chapter, we introduce the turnaround planning problem and the challenges it poses in integrated sites. We also introduce the background for the network design problem. In the second chapter, we study the financial impact of rescheduling turnarounds and the associated risk under unplanned outages. We compare the risk profiles presented by different production planning strategies. We propose a stochastic programming model for production planning that optimally builds up inventory ahead of time to hedge against production losses during unplanned outages. In the third chapter, we extend the stochastic optimization to handle a large set of scenarios and propose a Lagrangean decomposition method that improves a myopic production plan. The fourth chapter proposes a mixed-integer linear programming model that prescribes turnaround schedules when the underlying assets undergo yield loses and selectivity degradation. Here, we also study the impact of deferrals over a long-term horizon. The penultimate chapter addresses the nonlinear network design problem.The closing chapter summarizes the work and provides a few future directions. In the spirit of advancing manufacturing paradigms, the thesis supports investment in modeling efforts that address enterprise-wide planning problems.

The aim of this thesis was to create a resilient network, capable of handling link failures without affecting the data flow. This was done by using graph theory and three mathematical models. A generic system was created, on which the models were applied on. The mathematical models were path diversity, edge protection and path restoration. These models were tested to evaluate if they could create a robust system. The models were also compared with each other to obtain the best performing one. It was concluded that it was possible to construct a resilient network using these types of mathematical modelling. It was also concluded that the models provided different results in terms of cost and robustness. The report ends with suggestions on future work of how studies can be conducted to create realistic systems.

Höganäs AB's current distribution network for iron powder in the Asia Pacific (APAC) region is subject to high costs incurred by large inventories and high cost of capital. As a result of increasing demand and service level requirements from customers, inventories have steadily increased. Keeping a high inventory level has enabled high service levels irrespective of supply disruptions or changes in demand. It is important that the distribution network incorporates a balance between robustness and cost efficiency and not only focuses on one of these aspects. The purpose of this project is to provide Höganäs AB with scientific data on how the distribution network can be improved in terms of lowering the total cost of warehousing and distribution while maintaining or improving customer service. There are several goals for this project. The first goal is to optimize the flow of material in the distribution network given empirical data of customer demand. The intended model is a linear program. The linear program will solve a multi echelon, period, product, location and transportation mode instance of the distribution network design problem. The second goal is to test the robustness of the optimal solutions resulting from the linear program by stochastic simulation. The simulations utilize the optimal network designs generated by the linear program and is done for a set of possible scenarios where key parameters are changed. By adjusting key parameters and measuring the effect on cost and service level, the goal is to evaluate the robustness of each configuration. By keeping the existing nodes of the distribution network and changing the flow of material and distribution strategy, lower inventories can be maintained and service level kept high regardless of demand growth and supply disruption. The optimal distribution network design is one from the linear program, configured with a 14 day inventory level and 10 day reorder point for warehouses. The optimal design shows that distribution is made more robust and efficient by allowing for distribution between warehouses or supplying customers normally affiliated with other warehouses. It also suggests that a central redistribution warehouse is a possible improvement to the current network design. / Höganäs AB's nuvarande distributionsnätverket for järnpulver i Asien-Stillahavsregionen (APAC) är kostsamt till följd av höga lagernivåer och kapitalkostnader. Ökande efterfrågan och krav på hög servicenivå har inneburit en stadig ökning av lagernivåerna, vilket möjliggjort för företaget att upprätthålla servicenivån oberoende av störningar i leveranskedjan eller förändringar i efterfrågan. Det är viktigt att distributionsnätverket är balanserat avseende stabilitet och kostnadseffektivitet och inte endast optimeras avseende en av faktorerna. Syftet med projektet är förse Höganäs AB vetenskapligt understödd information om hur den totala kostnaden för distributionsnätverket kan sänkas samtidigt som kundservicen upprätthålls eller förbättras. Det finns flera mål för projektet. Det första målet är att optimera materialflödet i distributionsnätverket givet empiriska data över efterfrågan. Den avsedda modellen är ett linjärprogram som löser en instans av distributionsnätverkverksdesign-problemet med multipla lager, perioder, produkter, lokaliseringar och transportsätt. Det andra målet är att utvärdera stabiliteten hos de optimala lösningar som härrör från linjärprogrammet genom stokastisk simulering. Simuleringarna använder de optimala nätverksdesigner som genereras av det linjärprogrammet och genomförs för en uppsättning möjliga scenarier där nyckelparametrar ändras. Genom att justera nyckelparametrar och mäta effekten på kostnad och servicenivå är målet att utvärdera stabiliteten för varje konfiguration. Genom att behålla de befintliga noderna i distributionsnätverket och ändra materialflödet samt distributionsstrategin kan lägre lagernivåer uppnås och servicenivån hålls hög oavsett förändrad efterfrågan och störningar i leveranskedjan. Den optimala distributionsnätverkverksdesignen är en lösning från linjärprogrammet konfigurerat med 14 dagars lagernivå och 10 dagars beställningspunkt. Den optimala designen visar att distributionen görs mer stabil och effektiv genom att tillåta leveranser mellan lagerpunkterna eller att försörja kunder från andra lagerpunkter än de normalt försörjs från. Resultatet påvisar också att en strategiskt placerad omlastningscentral kan förbättra det nuvarande distributionsnätverket.

Water resources managers rely on information collected by hydrometric networks without a quantitative way to assess their efficiency, and most Canadian water monitoring networks still do not meet the minimum density requirements. There is also no established way to quantify the importance of each existing station in a hydrometric network. This research examines the properties of Combined Regionalization Dual Entropy Multi-Objective Optimization (CR-DEMO), a robust network design technique which combines the merits of information theory and multi-objective optimization. Another information theory based method called transinformation (TI) which can rank the contribution of unique information from each specific hydrometric station in the network is tested for use with CR-DEMO. When used in conjunction, these methods can not only provide an objective measure of network efficiency and the relative importance of each station, but also allow the user to make recommendations to improve existing hydrometric networks across Canada. The Ottawa River Basin, a major Canadian watershed in Ontario and Quebec, was selected for analysis. Various regionalization methods which could be used in CR-DEMO such as distance weighting and a rainfall runoff model were compared in a leave one out cross validation. The effect of removing stations with regulated and unnatural flow regimes from the regionalization process is also tested. The analysis is repeated on a smaller tributary of the Ottawa River Basin, the Madawaska Watershed, to examine scale effects in TI analysis and CR-DEMO application. In this study, tests were conducted to determine whether to include stations outside of the river basin in order to provide more context to the basin boundaries. It was found that the TI analysis complemented CR-DEMO well and it provided a detailed station ranking which was supported by CR-DEMO results. The inverse distance weighting drainage area ratio method was found to provide more accurate regionalization results compared to the rainfall-runoff model, and was thus chosen for CR-DEMO. Regionalization was shown to be more accurate when the regulated basins were omitted using leave one out cross validation. It was discovered that CR-DEMO is sensitive to scaling because some sub-basins which are relatively “well-equipped” compared to others in dire conditions may be penalized. The TI analysis was not as sensitive to scaling. Including stations outside of the Ottawa River Basin improved the information density and regionalization accuracy in the Madawaska Watershed because they provided context to sparse areas. Finally, Pareto optimal network solutions for both the Ottawa River Basin and the Madawaska Watershed were presented and analyzed. A number of optimal networks are proposed for each watershed along with “hot-spots” where new stations should be added whatever the end users’ choice of network. / Thesis / Master of Applied Science (MASc)

No description available.

This paper investigates the feasibility of the construction of a sustainable mixed-use development from a 1950's commercial plaza. The specific commercial plaza under investigation was University Plaza in Dundas, Ontario. Incorporating sustainable building techniques, such as higher density housing, clean energy generating technologies, energy efficiency, and water conservation, a more sustainable design for the plaza was accomplished. To become more pedestrian friendly, pedestrian areas were incorporated into the design, as well as a rapid transit terminal. Using rough construction estimates, it was determined that redevelopment would cost $67.9 million± 20% with a simple payback period of 7.8 years. Using the time value of money, a discounted payback period between 9.6 and 16.0 years was determined. As a result, the re-development project was deemed economically feasible to a reasonable degree. / Thesis / Master of Engineering (MEngr)

Two important areas of decision-making in distribution system design involve facility location and inventory policy determination. Facility location analyzes questions such as how many facilities should be opened, where they should be located, and which customers should be assigned to which DCs. Inventory policy determination involves more tactical decisions such as the order quantities and frequencies at each level or echelon in the network. It is believed that these two decisions can influence each other significantly. Including a multi-echelon inventory policy decision in a location analysis allows a user to capitalize on the strengths that each DC has to offer (e.g., lower labor rates, land costs, etc.). Likewise, when the locations of two facilities are known, a multi-echelon inventory policy can be designed better to incorporate the exact lead times and fixed costs between the facilities at each level of the system. Despite this, the two problems are typically solved independently. This research addresses these problems together and investigates different heuristic methods for solving a combined inventory-location model. We begin by presenting the background and formulation for each problem. These formulations are then combined to show how the two problems can be mathematically formulated together. Rather than solve the problem exactly, two heuristic methods using different philosophies are tested. We apply these heuristic methods to the combined inventory-location problem to determine how much we can improve distribution network design solutions and what type of heuristic methodology is most effective in gaining these improvements. Our results show that the combined inventory-location model is capable of improving on the solutions obtained by a location model with a fixed inventory policy. The improvement based on the data sets tested in this research was approximately $60,000. However, in cases where the inventory costs are a larger portion of the total cost, the improvement made by the inventory-location model increased to over $1,000,000. We also found that our second heuristic method tested provided statistically significant improved results over our first heuristic method. Moreover, the second heuristic method typically ran 67% faster. The improved results, although small in a relative sense (the average improvement was 0.18%), would still represent a large absolute improvement in supply chain costs. As much as $174,000 was saved in the data sets tested for this research. / Master of Science