An Algorithm for the Multidimensional Multiple-Choice Knapsack Problem

Martin MOSER  Dusan P.JOKANOVIC  Norio SHIRATORI  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E80-A   No.3   pp.582-589
Publication Date: 1997/03/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Systems and Control
Keyword: 
real-time configuration,  scheduling,  knapsack problem,  Lagrange multipliers,  

Full Text: PDF(633.4KB)
>>Buy this Article


Summary: 
In this paper we present an algorithm to solve an as-yet untreated knapsack problem, the Multidimensional Multiple-choice Knapsack Problem (MMKP). Since our specific application occurs in the real-time domain, a solution for the MMKP with a small upper bound on the runtime is desirable. Thus, the Lagrange multiplier method is chosen, and a heuristic with a worst-case runtime behavior better than O(n2m) is developed, n being the number of elements and m the number of dimensions. Extensive testing against an exact algorithm based on partial enumeration is used to establish the accuracy and efficiency of the heuristic.