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

• KDA performance is not significantly impacted by problem parameter values.
• Algorithm time increases superlinearly with increases in problem size.
• Algorithm time is approximately O(nlog(n)) with respect to knapsack problems.
• Knapsack generation using AER and ETP improves the quality of the KDA solution.
• Solution quality diminished using probabilistic and penalty constrained knapsacks.

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.