A dynamic programming approach to solving the multiple choice knapsack problem

MaRDI QIDQ761349zbMATH OpenFDO

Authors Krzysztof Dudzinski

Publication date 1984

Published in Bulletin of the Polish Academy of Sciences. Technical Sciences (Search for Journal in Brave)

zbMATH Keywords

computational complexityknapsack functionslinear relaxationmultiple choice knapsack problem

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Analysis of algorithms and problem complexity (68Q25) Boolean programming (90C09) Dynamic programming (90C39)

Review text

The paper deals with an algorithm based on computing knapsack functions for a multiple choice knapsack problem (MCK). The modification using the optimal solution of its linear relaxation is given and the computational complexity of the algorithm derived. First, MCK is described mathematically. A method similar to that of Gilmore and Gomory for solving 0-1 knapsack problems (KP) is given. This method is based on recursive computing of multiple choice knapsack functions. An algorithm for MCK exploiting the optimal solution of LMCK is derived and its computational complexity examined. If a heuristic solution obtained from the optimal solution is close to the optimal solution of MCK, then it may be better to apply this algorithm because of its smaller complexity. Otherwise, the general dynamic programming method for MCK may be used.

Recommendations

• scientific article; zbMATH DE number 3889280
• A minimal algorithm for the multiple-choice knapsack problem
• A hybrid dynamic programming/branch-and-bound algorithm for the multiple- choice knapsack problem
• The linear multiple choice knapsack problem
• A fast algorithm for the linear multiple-choice knapsack problem

Cited in

(13)

• Exact methods for the knapsack problem and its generalizations
• An effective dynamic programming algorithm for the minimum-cost maximal knapsack packing problem
• A hybrid dynamic programming/branch-and-bound algorithm for the multiple- choice knapsack problem
• Development of a hybrid dynamic programming approach for solving discrete nonlinear Knapsack problems
• Dynamic programming algorithms for the bi-objective integer knapsack problem
• A dynamic programming approach to the multiple-choice multi-period, knapsack problem and the recursive APL2 code
• scientific article; zbMATH DE number 3860891 (Why is no real title available?)
• Solution of multiple-choice knapsack problem encountered in high-level synthesis of vlsi circuits
• The multiple-choice multi-period knapsack problem
• scientific article; zbMATH DE number 1423920 (Why is no real title available?)
• Multiple criteria dynamic programming and multiple knapsack problem
• Large-Scale Scientific Computing
• Solving the linear multiple choice knapsack problem with two objectives: Profit and equity

This page was built for publication: A dynamic programming approach to solving the multiple choice knapsack problem

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