A branch and bound algorithm to solve large‐scale multistage stochastic programs with endogenous uncertainty. Issue 4 (20th November 2017)

• Record Type: Journal Article
• Authors: Christian, Brianna; Cremaschi, Selen
• Is Part Of: AIChE journal. Volume 64:Issue 4(2018)
• Page Start: 1262
• Page End: 1271
• Publication Date: 2017-11-20
• Subjects: multistage stochastic programming -- pharmaceutical clinical trial planning -- progressive hedging -- branch and bound -- endogenous uncertainty; Chemical engineering -- Periodicals; Génie chimique -- Périodiques; 660.28
• DOI: 10.1002/aic.16019
• Languages: English
• ISSNs: 0001-1541

Abstract

Abstract : 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. © 2017 American Institute of Chemical Engineers AIChE J, 64: 1262–1271, 2018