An improved direct descent algorithm for binary knapsack problems

DOI10.1016/0305-0548(89)90002-6MaRDI QIDQ1115799zbMATH OpenOpenAlexFDO

Authors Richard A. Murphy

Publication date 1989

Published in Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0305-0548(89)90002-6

zbMATH Keywords

binary knapsackcomputational testingdirect descent algorithmgeneral fathom and backtrack methodologyreduction tests

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Integer programming (90C10)

Review text

Several efficient algorithms for the solution of the binary knapsack problem have appeared in the literature. The direct descent algorithm is generally recognized as one of the most efficient. This paper improves the direct descent algorithm through a more general fathom and backtrack methodology and stronger reduction tests. The efficiency of these improvements is verified through extensive computational testing.

Recommendations

• A New Algorithm for the 0-1 Knapsack Problem
• Some computational results on real 0-1 knapsack problems
• scientific article; zbMATH DE number 432989
• scientific article; zbMATH DE number 3847214
• An algorithm for solving a class of knapsack problems and its generalization

Cites work

• A branch and bound algorithm for the generalized assignment problem
• A Direct Descent Binary Knapsack Algorithm
• Algorithm 37. Algorithm for the solution of the 0-1 single Knapsack problem
• An Algorithm for Large Zero-One Knapsack Problems
• An Efficient Algorithm for the 0-1 Knapsack Problem
• Computing Partitions with Applications to the Knapsack Problem
• Modeling Facility Location Problems as Generalized Assignment Problems
• Reduction Algorithm for Zero-One Single Knapsack Problems
• Some computational results on real 0-1 knapsack problems
• The Lagrangian Relaxation Method for Solving Integer Programming Problems

Cited in

(6)

• A hybrid dynamic programming/branch-and-bound algorithm for the multiple- choice knapsack problem
• Evolution of new algorithms for the binary knapsack problem
• Improved approximation algorithms for a bilevel knapsack problem
• Improved Generic Algorithms for Hard Knapsacks
• scientific article; zbMATH DE number 6263683 (Why is no real title available?)
• A modified descent method-based heuristic for binary quadratic knapsack problems with conflict graphs

This page was built for publication: An improved direct descent algorithm for binary knapsack problems

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