A branch and bound algorithm to solve large-scale multistage stochastic programs with endogenous uncertainty

The growth in computation complexity of multistage stochastic programs (MSSPs) with problem size often prevents its application to real-world size problems. We present two variants of branch-and-bound algorithm, which reduce the resource requirements for the generation and solution of large-scale MSSPs with endogenous uncertainty. Both variants use Knapsack-problem based Decomposition Algorithm (Christian and Cremaschi, Comput Chem Eng. 2015;74:34-47) to generate feasible solutions and primal bounds. First variant (PH-KDA) uses a progressive hedging dual-bounding approach; the second (OSS-KDA) solves the MSSP removing all nonanticipativity constraints. Both variants were used to solve several instances of the pharmaceutical clinical trial planning problem. The first iteration of both algorithms provides a feasible solution, and a primal bound and a dual bound for the problem. Although the dual-bounds of OSS-KDA were generally weaker than PH-KDA, they are generated considerably faster. For the seven-product case the OSS-KDA generated a solution with a gap of 9.92% in 115 CPU seconds. (c) 2017 American Institute of Chemical Engineers AIChE J, 64: 1262-1271, 2018