Heuristic and exact algorithms for the precedence-constrained knapsack problem (Q1586807)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Heuristic and exact algorithms for the precedence-constrained knapsack problem |
scientific article |
Statements
Heuristic and exact algorithms for the precedence-constrained knapsack problem (English)
0 references
7 November 2002
0 references
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.
0 references
knapsack problem
0 references
precedence constraints
0 references
dynamic programming algorithm
0 references
greedy heuristic
0 references
inverse precedence constrained knapsack problem
0 references