Seminars & Events

Mathematics and Computer Science Division
"New Approaches to Linear Programming with Probabilistic Constraints"

DATE: March 23, 2007
TIME: 10:30 am
SPEAKER: James Luedtke, PhD (Candidate) , Georgia Institute of Technology
LOCATION: Bldge: 221, Conference Room A216, Argonne National Laboratory
HOST: Mihai Anitescu

Description:
A classical approach to dealing with risk due to uncertainty in the constraint matrix of a linear program is to enforce that the constraints should be satisfied with high probability. Such problems, known as Linear Programs with Probabilistic Constraints, are generally intractable because calculating the probability that a given solution satisfies a constraint is in general hard, and the feasible region resulting from the probabilistic constraints is non-convex. We propose to use a sampling approach to address the probabilistic difficulty and mixed-integer programming techniques to address the non-convexity difficulty. In particular, we show that solving an approximate problem constructed from Monte Carlo samples from the underlying distribution can yield feasible solutions and optimality bounds for the original problem. A key enabler of this analysis is that the sample problem, while simplified from a probabilistic standpoint, is still non-convex. We therefore study a mixed-integer programming formulation of the sample problem, and show how it can be significantly strengthened in the special case in which only the right-hand side of the constraints is random. Computational results indicate that large-scale instances can be efficiently solved using this formulation.

Save the event to your calendar [schedule.ics]