Marco Laumanns

IBM Research – Zürich

Tuesday, November 03, 2015, 11:00 - 12:00

Room 01-012, Georges-Köhler-Allee 102, Freiburg 79110, Germany

Stochastic programs are usually formulated with probability distributions that are exogenously given. Modeling and solving models of endogenous uncertainty, where decisions can influence the probabilities, has remained a largely unresolved challenge. In this talk we present a new approach to handle endogenous uncertainty in stochastic programs for the case of decision-dependent probabilities, called distribution shaping. It enables an efficient characterization of decision-dependent probability measures based on the observation that neighboring probability measures in the space of the influencing binary decision variables, linearly related according to Bayes' Rule. Accordingly, we derive a successive polyhedral characterization of probability measures as a function of decisions and reformulate the corresponding nonlinear stochastic programs as mixed-integer programs. We demonstrate the effectiveness of the approach on two example problems. The first example is a pre-disaster planning problem of finding optimal investments to strengthen links in a transportation network, given that the links are subject to stochastic failure. Using the new approach, a recently considered instance of the Istanbul highway network can be solved to optimality within seconds, for which only approximate solutions have been known so far. The second example is a stochastic project planning problem, where individual activities have a risk of exceeding their allocated planned duration. This probability can be reduced by investing additional resources, and our approach allows to find an investment plan to that minimized expected project duration. 

This is joint work with Steve Prestwich (University College Cork), Ban Kawas (IBM Research) and Bruno Flach (IBM Research)