(419c) A Generalized Knapsack-Problem Based Decomposition Heuristic to Solve Large-Scale Multistage Stochastic Programs

Heuristic algorithms are one approach to address the computation complexity of multistage stochastic programs (MSSPs). Increases in the number of uncertain parameters or improving accuracy by adding addition possible realizations for each uncertain parameter causes exponential growth in problem size. Solutions to problems considered in literature are generally limited to cases considering between two and 15 uncertain parameters. When considering real-world size problems there can be hundreds of uncertain parameters. As such, several authors have explored the use of heuristics to generate good solutions for multistage stochastic programs. Colvin and Maravelias (2009) explored a rolling-horizon heuristic approach. The approach divides the planning horizon of the pharmaceutical clinical trial planning problem into a finite number of subsets and generates MSSPs for each subset. Gupta and Grossmann (2014) implemented a Lagrangean decomposition scheme using a scenario grouping strategy. The scenario grouping strategy allowed partial decomposition of the full space model. Scenarios are grouped based on differences in one endogenous parameter. The approach was applied to the oil field planning problem. More recently, Apap and Grossmann (2016) considered a sequential scenario decomposition strategy to solve MSSPs with endogenous and exogenous uncertainty. The strategy solved a series of endogenous problems to approximate the solution of the original problem. The authors tested the strategy using the oil field planning problem and the process synthesis problem.

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.

References

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