Title: Optimization under Uncertainty (Thesis Proposal)
Speaker: Vineet Goyal
When: November 29, 10:30am
Where: Room 388, Tepper School
Abstract
Most optimization problems in real life do not have accurate estimates of the problem parameters at the optimization phase. Stochastic optimization models have been studied widely in the literature to address this problem. The expected value optimization is reasonable in a repeated decision making framework. However, it does not sufficiently guard against the worst case future in more risk averse or one-shot applications. The broad purpose of this thesis is to study optimization approaches under uncertainty that overcome this shortcoming of a traditional stochastic optimization model.
We consider new models of uncertainty namely, the “demand-robust” model and the “chance constrained” model and introduce these in the framework of general covering problems. Here, uncertainty is considered in the right hand side of the constraints and is referred to as the demand uncertainty. In the two-stage model of “demand-robustness”, motivated by recent work in two-stage stochastic optimization problems, we are interested in finding a solution such that the worst case cost over all realizations of uncertainty is minimized. We prove a general structural lemma about special types of first stage solutions and provide approximation algorithms for covering problems such as Steiner tree, min-cut, minimum multi-cut, vertex cover and facility location. While some of the algorithms draw from the rounding approaches developed recently for stochastic optimization problems, we also show new applications of the old metric rounding techniques and develop novel charging arguments using Gomory-Hu cut trees for cut problems.
The robust optimization approach guards against the worst case future but tends to be overly conservative if there are some outlier scenarios. To overcome this, we consider a chance constrained model where we are given a reliability level p and the idea is to select a “p fraction” of the scenarios and find a robust solution on the selected scenarios. The remaining (1-p) fraction of the scenarios are considered as outliers and can be ignored. We consider both one-stage and two-stage chance constrained covering problems with demand-uncertainty. When the demand-uncertainty follows an independent distribution, we show that one-stage chance constrained covering problems reduce to a weighted version of well studied partial covering problems and we obtain constant approximations for the Steiner tree and facility location problems in this model. We also show hardness results for both one-stage and two-stage chance constrained problem in a “correlated” demand-uncertainty model.
In both the above models, we consider uncertainty in the right hand side of the constraints. We extend our work to consider uncertainty in the constraint matrix referred to as data uncertainty and propose to study a chance constrained knapsack problem where the size of each item is random. Finally, we propose to use the theoretical framework to develop a practical solution methodology to solve the planning problem for post-disaster logistics. This problem combines
aspects of both demand and data uncertainty. We aim to implement our solution to solve the real-life problem of earthquake preparedness of Turkey and Israel where seismic risk is a major concern.
