The problem of risk-averse decision making under uncertainties is studied from both modeling and computational perspectives. First, we consider a framework for constructing coherent and convex measures of risk which is inspired by infimal convolution operator, and prove that the proposed approach constitutes a new general representation of these classes. We then discuss how this scheme may be effectively employed to obtain a class of certainty equivalent measures of risk that can directly incorporate decision maker's preferences as expressed by utility functions. This approach is consequently utilized to introduce a new family of measures, the log-exponential convex measures of risk. Conducted numerical experiments show that this family can be a useful tool when modeling risk-averse decision preferences under heavy-tailed distributions of uncertainties. Next, numerical methods for solving the rising optimization problems are developed. A special attention is devoted to the class p-order cone programming problems and mixed-integer models. Solution approaches proposed include approximation schemes for $p$-order cone and more general nonlinear programming problems, lifted conic and nonlinear valid inequalities, mixed-integer rounding conic cuts and new linear disjunctive cuts.

This thesis presents a multi-stage linear stochastic mixed integer programming (SMIP) model for planning power generation in a pool-type day-ahead electricity market. The model integrates a reserve demand curve and shares most of the features of a stochastic unit commitment (UC) problem, which is known to be NP-hard. We capture the stochastic nature of the problem through scenarios, resulting in a large-scale mixed integer programming (MIP) problem that is computationally challenging to solve. Given that an independent system operator (ISO) has to solve such a problem within a time requirement of an hour or so, in order to release operating schedules for the next day real-time market, the problem has to be solved efficiently. For that purpose, we use some approximations to maintain the linearity of the model, parsimoniously select a subset of scenarios, and invoke realistic assumptions to keep the size of the problem reasonable. Even with these measures, realistic-size SMIP models with binary variables in each stage are still hard to solve with exact methods. We, therefore, propose a scenario-rolling heuristic to solve the SMIP problem. In each iteration, the heuristic solves a subset of the scenarios, and uses part of the obtained solution to solve another group in the subsequent iterations until all scenarios are solved. Two numerical examples are provided to test the performance of the scenario-rolling heuristic, and to highlight the difference between the operative schedules of a deterministic model and the SMIP model. Motivated by previous studies on pricing MIP problems and their applications to pricing electric power, we investigate pricing issues and compensation schemes using MIP formulations in the second part of the thesis. We show that some ideas from the literature can be applied to pricing energy/reserves for a relatively realistic model with binary variables, but some are found to be impractical in the real world. We propose two compensation schemes based on the SMIP that can be easily implemented in practice. We show that the compensation schemes with make-whole payments ensure that generators can have non-negative profits. We also prove that under some assumptions, one of the compensation schemes has the interesting theoretical property of minimizing the variance of the profit of generators to zero. Theoretical and numerical results of these compensation schemes are presented and discussed.

This thesis presents a multi-stage linear stochastic mixed integer programming (SMIP) model for planning power generation in a pool-type day-ahead electricity market. The model integrates a reserve demand curve and shares most of the features of a stochastic unit commitment (UC) problem, which is known to be NP-hard. We capture the stochastic nature of the problem through scenarios, resulting in a large-scale mixed integer programming (MIP) problem that is computationally challenging to solve. Given that an independent system operator (ISO) has to solve such a problem within a time requirement of an hour or so, in order to release operating schedules for the next day real-time market, the problem has to be solved efficiently. For that purpose, we use some approximations to maintain the linearity of the model, parsimoniously select a subset of scenarios, and invoke realistic assumptions to keep the size of the problem reasonable. Even with these measures, realistic-size SMIP models with binary variables in each stage are still hard to solve with exact methods. We, therefore, propose a scenario-rolling heuristic to solve the SMIP problem. In each iteration, the heuristic solves a subset of the scenarios, and uses part of the obtained solution to solve another group in the subsequent iterations until all scenarios are solved. Two numerical examples are provided to test the performance of the scenario-rolling heuristic, and to highlight the difference between the operative schedules of a deterministic model and the SMIP model. Motivated by previous studies on pricing MIP problems and their applications to pricing electric power, we investigate pricing issues and compensation schemes using MIP formulations in the second part of the thesis. We show that some ideas from the literature can be applied to pricing energy/reserves for a relatively realistic model with binary variables, but some are found to be impractical in the real world. We propose two compensation schemes based on the SMIP that can be easily implemented in practice. We show that the compensation schemes with make-whole payments ensure that generators can have non-negative profits. We also prove that under some assumptions, one of the compensation schemes has the interesting theoretical property of minimizing the variance of the profit of generators to zero. Theoretical and numerical results of these compensation schemes are presented and discussed.

This thesis is a study of the geometric design of solar concentrating collectors. In this work, a numerical optimization methodology was developed and applied to various problems in linear solar concentrator design, in order to examine overall optimization success as well as the effect of various strategies for improving computational efficiency. Optimization is performed with the goal of identifying the concentrator geometry that results in the greatest fraction of incoming solar radiation absorbed at the receiver surface, for a given collector configuration. Surfaces are parametrically represented in two-dimensions, and objective function evaluations are performed using various Monte Carlo ray-tracing techniques. Design optimization is performed using a gradient-based search scheme, with the gradient approximated through finite-difference estimation and updates based on the direction of steepest-descent. The developed geometric optimization methodology was found to perform with mixed success for the given test problems. In general, in every case a significant improvement in performance was achieved over that of the initial design guess, however, in certain cases, the quality of the identified optimal geometry depended on the quality of the initial guess. It was found that, through the use of randomized quasi-Monte Carlo, instead of traditional Monte Carlo, overall computational time to converge is reduced significantly, with times typically reduced by a factor of four to six for problems assuming perfect optics, and by a factor of about 2.5 for problems assuming realistic optical properties. It was concluded that the application of numerical optimization to the design of solar concentrating collectors merits additional research, especially given the improvements possible through quasi-Monte Carlo techniques.

In this thesis, we study a series of closely related multi-stage stochastic programming models in production planning, from both a modeling and an algorithmic point of view. We first consider a very simple multi-stage stochastic lot-sizing problem, involving a single item with no fixed charge and capacity constraint. Although a multi-stage stochastic integer program, this problem can be shown to have a totally unimodular constraint matrix. We develop primal and dual algorithms by exploiting the problem structure. Both algorithms are strongly polynomial, and therefore much more efficient than the Simplex method. Next, motivated by applications in semiconductor tool planning, we develop a general capacity planning problem under uncertainty. Using a scenario tree to model the evolution of the uncertainties, we present a multi-stage stochastic integer programming formulation for the problem. In contrast to earlier two-stage approaches, the multi-stage model allows for revision of the capacity expansion plan as more information regarding the uncertainties is revealed. We provide analytical bounds for the value of multi-stage stochastic programming over the two-stage approach. By exploiting the special simple stochastic lot-sizing substructure inherent in the problem, we design an efficient approximation scheme and show that the proposed scheme is asymptotically optimal. We conduct a computational study with respect to a semiconductor-tool-planning problem. Numerical results indicate that even an approximate solution to the multi-stage model is far superior to any optimal solution to the two-stage model. These results show that the value of multi-stage stochastic programming for this class of problem is extremely high. Next, we extend the simple stochastic lot-sizing model to an infinite horizon problem to study the planning horizon of this problem. We show that an optimal solution of the infinite horizon problem can be approximated by optimal solutions of a series of finite horizon problems, which implies the existence of a planning horizon. We also provide a useful upper bound for the planning horizon.

In order to achieve stable and sustainable systems for recycling post-consumer goods, it is frequently necessary to concentrate the flows from many collection points to meet the volume requirements for the recycler. This motivates the importance of growing the collection network over time to both meet volume targets and keep costs to a minimum. This research addresses a complex and interconnected set of strategic and tactical decisions that guide the growth of reverse supply chain networks over time. This dissertation has two major components: a tactical recruitment model and a strategic investment model. These capture the two major decision levels for the system, the former for the regional collector who is responsible for recruiting material sources to the network, the latter for the processor who needs to allocate his scarce resources over time and to regions to enable the recruitment to be effective. The recruitment model is posed as a stochastic dynamic programming problem. An exact method and two heuristics are developed to solve this problem. A numerical study of the solution approaches is also performed. The second component involves a key set of decisions on how to allocate resources effectively to grow the network to meet long term collection targets and collection cost constraints. The recruitment problem appears as a sub-problem for the strategic model and this leads to a multi-time scale Markov decision problem. A heuristic approach which decomposes the strategic problem is proposed to solve realistically sized problems. The numerical valuations of the heuristic approach for small and realistically sized problems are then investigated.

Public debt managers have a certain range of borrowing instruments varying in their interest rate type, currency, maturity etc. at their disposal and have to find an appropriate combination of those while raising debt on behalf of the government. In selecting the combination of instruments to be issued, i.e. the borrowing strategy to be pursued for a certain period of time, debt managers need to consider several objectives that are conflicting by their nature, and the uncertainty associated with the outcomes of the decisions made. The objective of this thesis is to propose an approach to support the decision making process regarding sovereign debt issuance. We incorporate Multi-Criteria Decision Making (MCDM) tools using a multi-period stochastic programming model that takes into account sequential decisions concerned with debt issuance policies. The model is then applied for public debt management in Turkey.

Not available / text

Fluid networks are useful tools for analyzing complex manufacturing environments especially in semiconductor wafer fabrication. The makespan of a fluid network is defined as the time to drain the system, when there is fluid present in the buffers initially. Based on this definition, the question of determining the allocation of resources so as to minimize the makespan of a fluid network is known as the makespan problem. In the deterministic version of the makespan problem, it is assumed that the parameters of the system, such as incoming rates, service rates and initial inventory, are known deterministically. The deterministic version of the makespan problem for reentrant lines and multiclass fluid networks has been investigated in the literature and an analytical solution for the problem is well-known. In this work, we provide another formulation for the deterministic makespan problem and prove that the problem can be solved for each station separately. Optimal solutions for the deterministic makespan problem have been used as a guide to develop heuristics methods to solve makespan scheduling problem in the job-shop context in the literature. This provides one motivation for further investigation of the fluid makespan problem. In this work our main focus is solving the makespan problem when the problem parameters are uncertain. This uncertainty may be caused by various factors such as the unpredictability of the arrival process or randomness in machine availability due to failures. In the presence of parameter uncertainty, the decision maker's goal is to optimally allocate the capacity in order to minimize the expected value of the makespan. We assume that the decision maker has distributional information about the parameters at the time of decision making. We consider two decision making schemes. In the first scheme, the controller sets the allocations before observing the parameters. After the initial allocations are set, they cannot be changed. In the second scheme, the controller is allowed a recourse action after a data collection process. It is shown that in terms of obtaining the optimal control, both schemes differ considerably from the deterministic version of the problem. We formulate both schemes using stochastic programming techniques. The first scheme is easier to analyze since the resulting model is convex. Unfortunately, under the second decision scheme, the objective function is non-convex. We develop a branch-and-bound methodology to solve the resulting stochastic non-convex program. Finally, we identify some special cases where the stochastic problem is analytically solvable. This work uses stochastic programming techniques to formulate and solve a problem arising in queueing networks. Stochastic programming and queueing systems are two major areas of Operations Research that deal with decision making under uncertainty. To the best of our knowledge, this dissertation is one of the first works that brings these two major areas together.

We take a novel perspective on real-life decision making problems involving binary activity-selection decisions that compete for scarce resources. The current literature in operations research approaches these problems by forming an optimal portfolio of activities that meets the specified resource constraints. However, often practitioners in industry and government do not take the optimal-portfolio approach. Instead, they form a rank-ordered list of activities and select those that have the highest priority. The academic literature tends to discredit such ranking schemes because they ignore dependencies among the activities. Practitioners, on the other hand, sometimes discredit the optimal-portfolio approach because if the problem parameters change, the set of activities that was once optimal no longer remains optimal. Even worse, the new optimal set of activities may exclude some of the previously optimal activities, which they may have already selected. Our approach takes both viewpoints into account. We rank activities considering both the uncertainty in the problem parameters and the optimal portfolio that will be obtained once the uncertainty is revealed. We use stochastic integer programming as a modeling framework. We develop several mathematical formulations and discuss their relative merits, comparing them theoretically and computationally. We also develop cutting planes for these formulations to improve computation times. To be able to handle larger real-life problem instances, we develop parallel branch-and-price algorithms for a capital budgeting application. Specifically, we construct a column-based reformulation, develop two branching strategies and a tabu search-based primal heuristic, propose two parallelization schemes, and compare these schemes on parallel computing environments using commercial and open-source software. We give applications of prioritization in facility location and capital budgeting problems. In the latter application, we rank maintenance and capital-improvement projects at the South Texas Project Nuclear Operating Company, a two-unit nuclear power plant in Wadsworth, Texas. We compare our approach with several ad hoc ranking schemes similar to those used in practice. / text