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.

Optimal investment decisions often rely on assumptions about the models and their associated parameter values. Therefore, it is essential to assess suitability of these assumptions and to understand sensitivity of outcomes when they are altered. More importantly, appropriate approaches should be developed to achieve a robust decision. In this thesis, we carry out a sensitivity analysis on parameter values as well as model speci cation of an important problem in portfolio management, namely the optimal portfolio execution problem. We then propose more robust solution techniques and models to achieve greater reliability on the performance of an optimal execution strategy. The optimal portfolio execution problem yields an execution strategy to liquidate large blocks of assets over a given execution horizon to minimize the mean of the execution cost and risk in execution. For large-volume trades, a major component of the execution cost comes from price impact. The optimal execution strategy then depends on the market price dynamics, the execution price model, the price impact model, as well as the choice of the risk measure. In this study, rst, sensitivity of the optimal execution strategy to estimation errors in the price impact parameters is analyzed, when a deterministic strategy is sought to minimize the mean and variance of the execution cost. An upper bound on the size of change in the solution is provided, which indicates the contributing factors to sensitivity of an optimal execution strategy. Our results show that the optimal execution strategy and the e cient frontier may be quite sensitive to perturbations in the price impact parameters. Motivated by our sensitivity results, a regularized robust optimization approach is devised when the price impact parameters belong to some uncertainty set. We rst illustrate that the classical robust optimization might be unstable to variation in the uncertainty set. To achieve greater stability, the proposed approach imposes a regularization constraint on the uncertainty set before being used in the minimax optimization formulation. Improvement in the stability of the robust solution is discussed and some implications of the regularization on the robust solution are studied. Sensitivity of the optimal execution strategy to market price dynamics is then investigated. We provide arguments that jump di usion models using compound poisson processes naturally model uncertain price impact of other large trades. Using stochastic dynamic programming, we derive analytical solutions for minimizing the expected execution cost under jump di usion models and compare them with the optimal execution strategies obtained from a di usion process. A jump di usion model for the market price dynamics suggests the use of Conditional Value-at-Risk (CVaR) as the risk measure. Using Monte Carlo simulations, a smoothing technique, and a parametric representation of a stochastic strategy, we investigate an approach to minimize the mean and CVaR of the execution cost. The devised approach can further handle constraints using a smoothed exact penalty function.

A workforce plan states the number of workers required at any point in time. Efficient workforce plans can help companies achieve their organizational goals while keeping costs low. In ever increasing globalized work market, companies need a competitive edge over their competitors. A competitive edge can be achieved by lowering costs. Labour costs can be one of the significant costs faced by the companies. Efficient workforce plans can provide companies with a competitive edge by finding low cost options to meet customer demand. This thesis studies the problem of determining the required number of workers when there are two categories of workers. Workers belonging to the first category are trained to work on one type of task (called Specialized Workers); whereas, workers in the second category are trained to work in all the tasks (called Flexible Workers). This thesis makes the following three main contributions. First, it addresses this problem when the demand is deterministic and stochastic. Two different models for deterministic demand cases have been proposed. To study the effects of uncertain demand, techniques of Robust Optimization and Robust Mathemat- ical Programming were used. The thesis also investigates methods to solve large instances of this problem; some of the instances we considered have more than 600,000 variables and constraints. As most of the variables are integer, and objective function is nonlinear, a commercial solver was not able to solve the problem in one day. Initially, we tried to solve the problem by using Lagrangian relaxation and Outer approximation techniques but these approaches were not successful. Although effective in solving small problems, these tools were not able to generate a bound within run time limit for the large data set. A number of heuristics were proposed using projection techniques. Finally this thesis develops a genetic algorithm to solve large instances of this prob- lem. For the tested population, the genetic algorithm delivered results within 2-3% of optimal solution.

Growing attention is being paid to the problem of efficiently designing and operating reverse supply chain systems to handle the return flows of production wastes, packaging, and end-of-life products. Because uncertainty plays a significant role in all fields of decision-making, solution methodologies for determining the strategic infrastructure of reverse production systems under uncertainty are required. This dissertation presents innovative optimization algorithms for designing a robust network infrastructure when uncertainty affects the outcomes of the decisions. In our context, robustness is defined as minimizing the maximum regret under all realization of the uncertain parameters. These new algorithms can be effectively used in designing supply chain network infrastructure when the joint probability distributions of key parameters are unknown. These algorithms only require the information on potential ranges and possible discrete values of uncertain parameters, which often are available in practice. These algorithms extend the state of the art in robust optimization, both in the structure of the problems they address and the size of the formulations. An algorithm for dealing with the problem with correlated uncertain parameters is also presented. Case studies in reverse production system infrastructure design are presented. The approach is generalizable to the robust design of network supply chain systems with reverse production systems as one of their subsystems.

In this study, we address the long-term project pricing problem for a company that operates in the defense industry. The pricing problem is a bid project pricing problem which includes various technical and financial uncertainties, such as estimations of workhour content of the project and exchange &amp / inflation rates. We propose a Robust Optimization (RO) approach that can deal with the uncertainties during the project lifecycle through the identification of several discrete scenarios. The bid project&rsquo / s performance measures, other than the monetary measures, for R&amp / D projects are identified and the problem is formulated as a multi-attribute utility project pricing problem. In our RO approach, the bid pricing problem is decomposed into two parts which are v solved sequentially: the Penalty-Model, and the RO model. In the Penalty-Model, penalty costs for the possible violations in the company&rsquo / s workforce level due to the bid project&rsquo / s workhour requirements are determined. Then the RO model searches for the optimum bid price by considering the penalty cost from the Penalty-Model, the bid project&rsquo / s performance measures, the probability of winning the bid for a given bid price and the deviations in the bid project&rsquo / s cost. Especially for the R&amp / D type projects, the model tends to place lower bid prices in the expected value solutions in order to win the bid. Thus, due to the possible deviations in the project cost, R&amp / D projects have a high probability of suffering from a financial loss in the expected value solutions. However, the robust solutions provide results which are more aware of the deviations in the bid project&rsquo / s cost and thus eliminate the financial risks by making a tradeoff between the bid project&rsquo / s benefits, probability of winning the bid and the financial loss risk. Results for the probability of winning in the robust solutions are observed to be lower than the expected value solutions, whereas expected value solutions have higher probabilities of suffering from a financial loss.

In this thesis, performance of relay-assisted Device-to-device (D2D) communication is investigated where D2D traffic is carried through relay nodes. I develop resource management schemes to maximize end-to-end rate as well as conversing rate requirements for cellular and D2D UEs under total power constraint. I also develop a low-complexity distributed solution using the concept of message passing. Considering the uncertainties in wireless links (e.g., when interference from other relay nodes and the link gains are not exactly known), I extend the formulation using robust resource allocation techniques. In addition, a distributed solution approach using stable matching is developed to allocate radio resources in an efficient and computationally inexpensive way under the bounded channel uncertainties. Numerical results show that, there is a distance threshold beyond which relay-assisted D2D communication significantly improves network performance at the cost of small increase in end-to-end delay when compared to conventional approach.

Stochastic programming is a mathematical technique for decision making under uncertainty using probabilistic statements in the problem objective and constraints. In practice, the distribution of the unknown quantities are often known only through observed or simulated data. This dissertation discusses several methods of using this data to formulate, solve, and evaluate the quality of solutions of stochastic programs. The central contribution of this dissertation is to investigate the use of techniques from simulation and statistics to enable data-driven models and methods for stochastic programming. We begin by extending the method of overlapping batches from simulation to assessing solution quality in stochastic programming. The Multiple Replications Procedure, where multiple stochastic programs are solved using independent batches of samples, has previously been used for assessing solution quality. The Overlapping Multiple Replications Procedure overlaps the batches, thus losing the independence between samples, but reducing the variance of the estimator without affecting its bias. We provide conditions under which the optimality gap estimators are consistent, the variance reduction benefits are obtained, and give a computational illustration of the small-sample behavior. Our second result explores the use of phi-divergences for distributionally robust optimization, also known as ambiguous stochastic programming. The phi-divergences provide a method of measuring distance between probability distributions, are widely used in statistical inference and information theory, and have recently been proposed to formulate data-driven stochastic programs. We provide a novel classification of phi-divergences for stochastic programming and give recommendations for their use. A value of data condition is derived and the asymptotic behavior of the phi-divergence constrained stochastic program is described. Then a decomposition-based solution method is proposed to solve problems computationally. The final portion of this dissertation applies the phi-divergence method to a problem of water allocation in a developing region of Tucson, AZ. In this application, we integrate several sources of uncertainty into a single model, including (1) future population growth in the region, (2) amount of water available from the Colorado River, and (3) the effects of climate variability on water demand. Estimates of the frequency and severity of future water shortages are given and we evaluate the effectiveness of several infrastructure options.

Water supply system planning is concerned about the design of water supply infrastructure for distributing water from sources to users. Population growth, economic development and diminishing freshwater supplies are posing growing challenges for water supply system planning in many urban areas. Besides the need to exploit alternative water sources to the conventional surface and groundwater supplies, such as reclaimed water, a systematic point of view has to be taken for the efficient management of all potential water resources, so that issues of water supply, storage, treatment and reuse are not considered separately, but rather in the context of their interactions. The focus of this dissertation is to develop mathematical models and optimization algorithms for water supply system planning, where the interaction of different system components is explicitly considered. A deterministic nonlinear programming model is proposed at first to decide pipe and pump sizes in a regional water supply system for satisfying given potable and non-potable user demands over a certain planning horizon. A branch-and-bound algorithm based on the reformulation-linearization technique is then developed for solving the model to global optimality. To handle uncertainty in the planning process, a stochastic programming (SP) model and a robust optimization (RO) model are successively proposed to deal with random water supply and demand and the risk of facility failure, respectively. Both models attempt to make the decision of building some additional treatment and recharge facilities for recycling wastewater on-the-site. While the objective of the SP model is to minimize the total system design and expected operation cost, the RO model tries to achieve a favorable trade-off between system cost and system robustness, where the system robustness is defined in terms of meeting given user demands against the worst-case failure mode. The Benders decomposition method is then applied for solving both models by exploiting their special structure.

Observers are used in the monitoring and control of dynamical systems to deduce the values of unmeasured states. Designing an observer requires having an accurate model of the plant — if the model parameters are characterized imprecisely, the observer may not provide reliable estimates. An interval observer, which comprises an upper and lower observer, bounds the plant's states from above and below, given the range of values of the imprecisely characterized parameters, i.e., it defines an interval in which the plant's states must lie at any given instant. We propose a linear programming-based method of interval observer design for two cases: 1) only the initial conditions of the plant are uncertain; 2) the dynamical parameters are also uncertain. In the former, we optimize the transient performance of the interval observers, in the sense that the volume enclosed by the interval is minimized. In the latter, we optimize the steady state performance of the interval observers, in the sense that the norm of the width of the interval is minimized at steady state. Interval observers are typically designed to characterize the widest interval that bounds the states. This thesis proposes an interval observer design method that utilizes additional, but still-incomplete information, that enables the designer to identify tighter bounds on the uncertain parameters under certain operating conditions. The number of bounds that can be refined defines a class of systems. The definition of this class is independent of the specific parameters whose bounds are refined. Applying robust optimization techniques, under a cardinality constrained model of uncertainty, we design a single observer for an entire class of systems. These observers guarantee a minimum level of performance with respect to the aforementioned metrics, as we optimize the worst-case performance over a given class of systems. The robust formulation allows the designer to tune the level of uncertainty in the model. If many of the uncertain parameter bounds can be refined, the nominal performance of the observer can be improved, however, if few or none of the parameter bounds can be refined, the nominal performance of the observer can be designed to be more conservative.

Markov decision processes (MDPs) have proven to be a useful model for sequential decision- theoretic reasoning under uncertainty, yet they require the specification of a reward function that can require sophisticated human judgement to assess relevant tradeoffs. This dissertation casts the problem of specifying rewards as one of preference elicitation and aims to minimize the degree of precision with which a reward function must be specified while still allowing optimal or near-optimal policies to be produced. We demonstrate how robust policies can be computed for MDPs given only partial reward information using the minimax regret criterion. Minimax regret offers an intuitive bound on loss; however, it is computationally intractable in general. This work develops techniques for exploiting MDP structure to allow for offline precomputation that enables efficient online minimax regret computation. To complement this exact approach we develop several general approximations that offer both upper and lower bounds on minimax regret. We further show how approximations can be improved online during the elicitation procedure to balance accuracy and efficiency. To effectively reduce regret, we investigate a spectrum of elicitation approaches that range from the computationally-demanding optimal selection of complex queries about full MDP policies (which are informative, but, we believe, cognitively difficult) to the heuristic selection of simple queries that focus on a small set of reward parameters. Results are demonstrated on MDPs drawn from the domains of assistive technology and autonomic computing. Finally we demonstrate our framework on a realistic website optimization domain, per- forming elicitation on websites with tens of thousands of webpages. We show that minimax regret can be efficiently computed, and develop informative and cognitively reasonable queries that quickly lower minimax regret, producing policies that offer significant improvement in the design of the underlying websites.