Friday, September 16, 2005
2:00 pm Posner Hall 259
Vineet Goyal
Tepper School of Business
Title:
Approximation Algorithms for Demand-Robust and Data-Robust Optimization Problems
Abstract:
Robust Optimization has traditionally focused on uncertainty in data and costs in optimization problems to formulate models whose solutions will be optimal in the worst case among the various uncertain scenarios in the model. However besides the costs, uncertainty can also be in the problem constraints or “demand”. To model such uncertainty demand-robust versions of common optimization problems were recently introduced (Dhamdhere et al., FOCS 2005) motivated by worst-case considerations of two-stage stochastic optimization models. We consider the shortest path and minimum spanning tree problems under demand-robust and data-robust models and give approximation algorithms for the same.
In this talk, I would present the improved approximation algorithm for the demand-robust shortest path problem which improves the approximation factor from 16 to 7.1. I would also present some hardness results for the data-robust models.
This is joint work with R. Ravi.
John Turner
Tepper School of Business
Title:
Robust Solutions for Some Special Cases of the Resource-Constrained Project Scheduling Problem
Abstract:
In the pursuit of robust solutions to the Resource Constrained Project Scheduling Problem, we introduce the robust objective $\sum_i Pred(i)$, which counts the total number of precedence relationships in a schedule. We focus on the special case of RCPSP that has a single resource and whose temporal constraints are precedence constraints. In the standard notation, this problem is $PS1|prec|\sum_i Pred(i)$. To our knowledge, this objective has not been previously studied in the context of project scheduling. By employing a generalization of Dilworth’s Theorem, we develop a MILP and then suggest the use of Bender’s Decomposition to solve this MILP. The use of Bender’s Decomposition is justified by the fact that the Bender’s subproblem in our case is a network flow problem, which can be solved very quickly. We then conclude with some symmetry-breaking and min-forbidden-set-breaking constraints that may be added to the master problem ILP to speed up solution time.
