We propose a new method, based on semidefinite optimization, to find tight upper bounds on the expected project completion time and expected project tardiness in a stochastic project scheduling environment, when only limited information in the form of first and second (joint) moments of the durations of individual activities in the project is available. Our computational experiments suggest that the bounds provided by the new method are stronger and often significant compared to the bounds found by alternative methods. / Singapore-MIT Alliance (SMA)

<p>Optimization under uncertainty is the field of optimization where the data or the optimization model itself has uncertainties associated with it. Such problems are more commonly referred to as stochastic optimization problems. These problems capture the broad idea of making optimal decisions under uncertainty. An important class of these stochastic optimization problems is chance-constrained optimization problems, where the decision maker seeks to choose the best decision such that the probability of violating a set of uncertainty constraints is within a predefined probabilistic threshold risk level. Such stochastic optimization problems have found a lot of interest in the service industry as the service providers need to satisfy a minimum service level agreement (SLA) with their customers. Satisfying SLA in the presence of uncertainty in the form of probabilistic failure of infrastructure poses many interesting and challenging questions. In this thesis, we answer a few of these questions.</p> <p>We first explore the problem of quantifying uncertainties that adversely impact the service provider's infrastructure, thereby hurting the service level agreements. In particular we address the probability quantification problem, where given an uncertainty set, the goal is to quantify the probability of an event, on which the optimal value of an optimization problem exceeds a predefined threshold value. The novel techniques we propose, use and develop ideas from diverse literatures such as mixed integer nonlinear program, chance-constrained programming, approximate sampling and counting techniques, and large deviation bounds. Our approach yields the first polynomial time approximation scheme for the specific probability quantification problem we consider. </p> <p>Our next work is inspired by the ideas of risk averse decision making. Here, we focus on studying the problem of minimizing risk functions. As a special case we also explore the problem of minimizing the Value at Risk (VaR), which is a well know non-convex problem. For more than a decade, the well-known, best convex approximation to this problem has been obtained by minimizing the Conditional Value at Risk (CVaR). We proposed a new two-stage model which formulates these risk functions, which eventually leads to a bilinear optimization problem, a special case of which is the VaR minimization problem. We come up with enhancements to this bilinear formulation and use convexification techniques to obtain tighter lower and upper convex approximations to the problem. We also find that the approximation obtained by CVaR minimization is a special case of our method. The overestimates we construct help us to develop tighter convex inner approximations for the chance constraint optimization problems.</p>