European J of Industrial Engineering · 2010 · 22 citations · 11 references
Natural SciencesOperations ManagementDesign OptimizationOptimizationSchedulingBranch And BoundCombinatorial OptimizationConstrained OptimizationDiscrete OptimizationDynamic ProgrammingHeuristic OptimizationCombinatorial Optimization HeuristicsHeuristic AlgorithmsKnapsack Problems
This article presents an exact cooperative method for the solution of the multidimensional knapsack problem (MKP) which combines dynamic programming and branch and bound. Our method makes cooperate a dynamic programming heuristics based on surrogate relaxation and a branch and bound procedure. Our algorithm was tested for several randomly generated test sets and problems in the literature. Solution values of the first step are compared with optimal values and results provided by other well-known existing heuristics. Then, our exact cooperative method is compared with a classical branch and bound algorithm. [Received 8 October 2008; Revised 28 May 28 2009; Revised 10 December 2009; Accepted 11 December 2009]
11
A Branch and Bound Algorithm for the Knapsack Problem
Peter Kolesar · Management Science · 1967 · 209 citations