A Branch and Cut Framework for Multi-Stage Stochastic Programming Problems Under Endogenous Uncertainty

To ensure that decisions in multi-stage stochastic programming (MSSP) formulations do not anticipate future outcomes, it is necessary to introduce nonanticipativity constraints (NACs). In the case of endogenous uncertainty, NACs grow very quickly making all but the smallest multi-stage stochastic programming models computationally intractable. To address this challenge, we first present a number of theoretical results that allow us to formulate substantially smaller and tighter MSSP models. Second, we discuss a branch and cut algorithm where necessary inequality NACs are removed from the starting formulation and added only if they are violated. Our theoretical results coupled with the proposed algorithm allow us to generate and solve problems that were previously intractable. The methods were applied to the resource-constrained scheduling of clinical trials in the pharmaceutical research and development pipeline.