Heuristic and exact algorithms for the precedence-constrained knapsack problem (Q1586807)

Consider an acyclic digraph where a weight and a profit are associated with every vertex. The precedence constrained knapsack problem packs vertices in a knapsack subject to the additional constraint that a vertex can only be packed if all its predecessors are also packed. As in the classical knapsack problem the profit (sum of single vertex profits) is to be maximized, but the total weight of all packed vertices must not be greater than a specified bound. The authors design a dynamic programming algorithm for the precedence constrained knapsack problem. The solution procedure can be speeded up by applying first a greedy heuristic and by using two simple rules for fixing variables. Finally, the inverse precedence constrained knapsack problem is considered.