Intellectual Merit - For most applications in which optimization algorithms are employed in industry, the input data is actually not known. This might be because the data is based on measurements, which are estimates due to noise, or because only a forecast of future data is available. Stochastic optimization models incorporate this uncertainty as part of the input, and are harder to solve than their deterministic counterparts. This research investigates algorithms that compute provably near-optimal solutions for stochastic optimization problems; in contrast, traditional approaches mostly show convergence results without guarantees to efficiently produce near-optimal solutions. Broader Impact - Finding good approaches to gain new efficiencies in logistical planning is important for the overall US economy. This research develops new algorithmic techniques to do this. By studying simplified models, this research devises algorithmic paradigms that can then be applied in more concrete applications, thereby providing industry with better solutions. Furthermore, it is important that the US workforce has sufficient expertise to meet the technological challenges of the coming century, and by integrating this research with the training of both graduate and undergraduate students, this work helps to meet this need in maintaining the economic competitiveness of the US.
This research addresses a number of specific discrete stochastic optimization problems, focusing primarily on problems from logistics: routing, scheduling, inventory management and network design. This research focuses on a "black box" that specifies the probabilistic input by means of polynomial independent samples from the underlying distribution; this is important when one has access to historical data. This work studies the stochastic TSP, max cut, and single-machine scheduling problems; 2-stage with recourse models of the survivable network design and maximum job selection problems, and multistage stochastic models from inventory control, options pricing, and AdWords bidding. This research also studies the deterministic asymmetric TSP, bin-packing, and capacitated facility-location problems.
