Heuristic and exact algorithms for the precedence-constrained knapsack problem

DOI10.1023/A:1004649425222MaRDI QIDQ1586807zbMATH OpenOpenAlexFDO

Authors R. Smith

Publication date 7 November 2002

Published in Journal of Optimization Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1023/a:1004649425222

zbMATH Keywords

dynamic programming algorithmgreedy heuristicinverse precedence constrained knapsack problemknapsack problemprecedence constraints

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

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.

Recommendations

• A pegging approach to the precedence-constrained knapsack problem
• Polyhedral results for the precedence-constrained knapsack problem
• scientific article; zbMATH DE number 1895857
• Lifting cover inequalities for the precedence-constrained knapsack problem
• Large-scale multi-period precedence constrained knapsack problem: a mining application

Cites work

• A Depth-First Dynamic Programming Algorithm for the Tree Knapsack Problem
• Computing Partitions with Applications to the Knapsack Problem
• scientific article; zbMATH DE number 3650295 (Why is no real title available?)
• scientific article; zbMATH DE number 3126094 (Why is no real title available?)
• scientific article; zbMATH DE number 44282 (Why is no real title available?)
• scientific article; zbMATH DE number 193411 (Why is no real title available?)
• scientific article; zbMATH DE number 3633709 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1033260 (Why is no real title available?)
• scientific article; zbMATH DE number 1769298 (Why is no real title available?)
• Network flows. Theory, algorithms, and applications.
• On Knapsacks, Partitions, and a New Dynamic Programming Technique for Trees
• OPTIMAL TOOL MODULE DESIGN PROBLEM FOR NC MACHINE TOOLS
• The knapsack problem: A survey

Cited in

(10)

• Sequential testing of n-out-of-n systems: precedence theorems and exact methods
• Shift-and-merge technique for the DP solution of the time-constrained backpacker problem
• The knapsack problem with neighbour constraints
• A pegging approach to the precedence-constrained knapsack problem
• Piece selection algorithms for layered video streaming in P2P networks
• Exact and heuristic algorithms for dynamic tree simplification
• Large-scale multi-period precedence constrained knapsack problem: a mining application
• Heuristic and Exact Algorithms for the Interval Min–Max Regret Knapsack Problem
• Algorithms to solve the knapsack constrained maximum spanning tree problem
• Nonconvex piecewise linear knapsack problems

This page was built for publication: Heuristic and exact algorithms for the precedence-constrained knapsack problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1586807)