A dynamic programming approach to solving the multiple choice knapsack problem
type: Item
instance of: scholarly article
title: A dynamic programming approach to solving the multiple choice knapsack problem
zbMATH Open document ID: 0555.90075
author: Krzysztof Dudzinski
published in: Bulletin of the Polish Academy of Sciences. Technical Sciences
publication date: 1984-01-01T00:00:00Z
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.
Mathematics Subject Classification ID: 90C09
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 90C39
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 3885654
zbMATH Keywords: knapsack functions
zbMATH Keywords: multiple choice knapsack problem
zbMATH Keywords: linear relaxation
zbMATH Keywords: computational complexity
reviewed by: N.A.Warsi
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 3885654