2017/01/15 by Utz‐Uwe Haus, Haus, Utz-Uwe, Carla Michini +3
Computer Science · Decision Sciences · Engineering · #05C30 (Secondary) #90C15 (Primary) 90C11 #90C35 #Bayesian Modeling and Causal Inference #Complex Systems and Decision Making #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Infrastructure Resilience and Vulnerability Analysis #Optimization and Control (math.OC) #Reliability and Maintenance Optimization #Risk and Safety Analysis #Software Reliability and Analysis Research
paper · pdf · doi:10.48550/arxiv.1701.04055
openalex publication_date 2017/01/15 · openalex created_date 2022/10/03 · openalex updated_date 2026/07/28
Modeling decision-dependent scenario probabilities in stochastic programs is\ndifficult and typically leads to large and highly non-linear MINLPs that are\nvery difficult to solve. In this paper, we develop a new approach to obtain a\ncompact representation of the recourse function using a set of binary decision\ndiagrams (BDDs) that encode a nested cover of the scenario set. The resulting\nBDDs can then be used to efficiently characterize the decision-dependent\nscenario probabilities by a set of linear inequalities, which essentially\nfactorizes the probability distribution and thus allows to reformulate the\nentire problem as a small mixed-integer linear program. The approach is\napplicable to a large class of stochastic programs with multivariate binary\nscenario sets, such as stochastic network design, network reliability, or\nstochastic network interdiction problems. Computational results show that the\nBDD-based scenario representation reduces the problem size, and hence the\ncomputation time, significant compared to previous approaches.\n