  Modeling decision-dependent scenario probabilities in stochastic programs is
difficult and typically leads to large and highly non-linear MINLPs that are
very difficult to solve. In this paper, we develop a new approach to obtain a
compact representation of the recourse function using a set of binary decision
diagrams (BDDs) that encode a nested cover of the scenario set. The resulting
BDDs can then be used to efficiently characterize the decision-dependent
scenario probabilities by a set of linear inequalities, which essentially
factorizes the probability distribution and thus allows to reformulate the
entire problem as a small mixed-integer linear program. The approach is
applicable to a large class of stochastic programs with multivariate binary
scenario sets, such as stochastic network design, network reliability, or
stochastic network interdiction problems. Computational results show that the
BDD-based scenario representation reduces the problem size, and hence the
computation time, significant compared to previous approaches.

Optimization and Control;Discrete Mathematics