Distribution shaping and scenario bundling for stochastic programs with endogenous uncertainty

Abstract

Stochastic programs are usually formulated with probability distributions that are exogenously given. Modeling and solving problems withendogenous uncertainty, where decisions can influence the probabilities, has remained a largely unresolved challenge. In this paper we develop a new approach to handle decision-dependent probabilities based on the ideaof distribution shaping. It uses a sequence of distributions, successively conditioned on the influencing decision variables, and characterizes these by linear inequalities. We demonstrate the approach on a pre-disaster planning problem of finding optimal investments to strengthen links ina transportation network, given that the links are subject to stochastic failure. Our new approach solves a recently considered instance of the Istanbul highway network to optimality within seconds, for which only approximate solutions had been known so far.