Abstract:  Uncertainty is prevalent in real-world optimization problems. A classical approach to managing the risk associated with this uncertainty is to enforce probabilistic or chance constraints in the optimization model which require the selected solution to satisfy a desirable condition with high probability. Unfortunately, optimization with probabilistic constraints is computationally difficult due to the probabilistic nature of the problem and because the feasible region is usually not convex. We study how approximations based on random samples of the uncertain data can be used to construct solutions which satisfy the chance constraint, and also to estimate the quality of these solutions relative to the optimal solution. Although the sample approximation problem has a simplified probabilistic structure, it has a non-convex feasible region, and hence is still difficult to solve in general. Therefore, we study how to solve this problem using integer programming techniques in the special case in which the uncertainty appears only in the right-hand side of the constraint matrix. We report results from computational experiments testing this approach.


Jim Luedtke obtained his Ph.D. degree from Georgia Tech in 2007. His research interests include numerical methods for discrete and stochastic optimization problems, and their application to real-world problems. Dr. Luedtke is currently a postdoctoral researcher in the Business Analytics and Mathematical Sciences Division of IBM Research, and will be joining the Industrial Engineering faculty at the University of Wisconsin-Madison this fall.