Heuristic and exact algorithms for the precedence-constrained knapsack problem
type: Item
instance of: scholarly article
title: Heuristic and exact algorithms for the precedence-constrained knapsack problem
zbMATH Open document ID: 0997.90066
DOI: 10.1023/A:1004649425222
author: R. Smith
published in: Journal of Optimization Theory and Applications
publication date: 2002-11-07T00:00:00Z
review text: 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.
reviewed by: Rainer E. Burkard
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 1533374
zbMATH Keywords: knapsack problem
zbMATH Keywords: precedence constraints
zbMATH Keywords: dynamic programming algorithm
zbMATH Keywords: greedy heuristic
zbMATH Keywords: inverse precedence constrained knapsack problem
MaRDI profile type: Publication
cites work: Q3056948
cites work: Q4344098
cites work: Q4040221
cites work: Q4198056
cites work: The knapsack problem: A survey
cites work: Q3993418
cites work: On Knapsacks, Partitions, and a New Dynamic Programming Technique for Trees
cites work: Q4540048
cites work: A Depth-First Dynamic Programming Algorithm for the Tree Knapsack Problem
cites work: OPTIMAL TOOL MODULE DESIGN PROBLEM FOR NC MACHINE TOOLS
cites work: Q4194455
cites work: Q3241581
cites work: Q3208433
cites work: Computing Partitions with Applications to the Knapsack Problem
full work available at URL: a:1004649425222
OpenAlex ID: W1499020692
description: scientific article; zbMATH DE number 1533374