(419c) A Generalized Knapsack-Problem Based Decomposition Heuristic to Solve Large-Scale Multistage Stochastic Programs
In this presentation, we describe a generalized knapsack-problem based decomposition heuristic to solve large-scale multistage stochastic programs. The algorithm builds upon our previous work (Christian and Cremaschi, 2015), and it is expanded to accommodate multistage stochastic programs with both endogenous and exogenous uncertain with non-trivial recourse actions. The heuristic algorithm strategically solves a series of knapsack problems along the planning horizon of multistage stochastic programs. The items for the knapsack problems are constructed using the decision variables of the MSSP. The item values are estimated using the expected gains associated with the value of the decision variable. Constraints from the original MSSP are modified and persist as weight constraints on the knapsack problems. The heuristic starts by generating and solving a knapsack problem at the first time period. Based on the items selected as the solution of this first knapsack problem, uncertainty is realized, and new knapsack problems corresponding to each of these realizations are generated and solved. The algorithm terminated when the end of the planning horizon is reached.
We apply this generalized knapsack-problem based decomposition heuristic to solve three problems: (1) pharmaceutical clinical trial planning problem (Colvin and Maravelias, 2008), (2) artificial lift infrastructure planning problem (Zeng and Cremaschi, 2017), and (3) new technology investment planning problem, which seeks to determine the optimal investment strategy for new technology develop given uncertainty in the performance and success of the technology. The results show that, similar to the clinical trial planning problems solved in Christian and Cremaschi (2015), the generalized heuristic provides tight feasible solutions for the MSSPs of the new technology investment planning problems, and the optimum solutions for the MSSPs of the artificial lift planning problems. For all problems considered, the tight feasible solutions are generated several orders of faster than solving the original MSSPs.
Apap, R. M., & Grossmann, I. E. (2016). Models and Computational Strategies for Multistage Stochastic Programming under Endogenous and Exogenous Uncertainties. Computers & Chemical Engineering. https://doi.org/http://dx.doi.org/10.1016/j.compchemeng.2016.11.011
Christian, B., & Cremaschi, S. (2015). Heuristic solution approaches to the pharmaceutical R&D pipeline management problem. Computers and Chemical Engineering, 74, 34â47.
Colvin, M., & Maravelias, C. T. (2008). A stochastic programming approach for clinical trial planning in new drug development. Computers & Chemical Engineering, 32(11), 2626â2642. https://doi.org/http://dx.doi.org/10.1016/j.compchemeng.2007.11.010
Colvin, M., & Maravelias, C. T. (2009). Scheduling of testing tasks and resource planning in new product development using stochastic programming. Computers & Chemical Engineering, 33, 964â976. https://doi.org/10.1016/j.compchemeng.2008.09.010
Gupta, V., & Grossmann, I. E. (2014). Multistage stochastic programming approach for offshore oilfield infrastructure planning under production sharing agreements and endogenous uncertainties. Journal of Petroleum Science and Engineering, 124, 180â197. https://doi.org/10.1016/j.petrol.2014.10.006
Zeng Z, & Cremaschi S. Artificial lift infrastructure planning for shale gas producing horizontal wells. Foundations of Computer Aided Process Operations / Chemical Process Control, 2017