Variants to a knapsack decomposition heuristic for solving R&D pipeline management problems

作     者：Christian, Brianna Cremaschi, Selen 

作者机构：Auburn Univ Dept Chem Engn 212 Ross Hall Auburn AL 36849 USA 

出 版 物：《COMPUTERS & CHEMICAL ENGINEERING》 (计算机与化工)

年 卷 期：2017年第96卷

页      面：18-32页

核心收录：

学科分类：0817[工学-化学工程与技术] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Auburn University Hopper Cluster US National Science Foundation through Auburn University Integrative Graduate Research and Education Traineeship (IGERT) program NSF Career Grant Directorate For Engineering Div Of Chem, Bioeng, Env, & Transp Sys Funding Source: National Science Foundation 

主　　题：Multistage stochastic programming Pharmaceutical R&D pipeline management Decision dependent uncertainty Endogenous uncertainty Knapsack decomposition algorithm 

摘      要：The knapsack decomposition algorithm (KDA) (Christian and Cremaschi, 2015) decomposes the R&D pipeline management problem into a series of knapsack problems, which are solved along the planning horizon. It yields tight feasible solutions, and improves the solution times by several orders of magnitude for large instances. This paper investigates the impact of problem parameters and size, and KDA decision rules on KDA solution quality and time. The decision rules are (1) timing of new knapsack problem generations, and (2) formulation of the resource constraints in knapsack problems. The results revealed that the KDA decision trees were insensitive to problem parameters, and the KDA solution times grew super-linearly with linear increases in the length of the planning horizon and the number of products. The results suggest that the KDA where knapsack problems are generated after each realization with the original resource constraint yields the most accurate solutions in the quickest time. (C) 2016 Elsevier Ltd. All rights reserved.