For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
An Algorithm for the Multidimensional Multiple-Choice Knapsack Problem
Martin MOSER Dusan P.JOKANOVIC Norio SHIRATORI
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1997/03/25
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Systems and Control
real-time configuration, scheduling, knapsack problem, Lagrange multipliers,
Full Text: PDF(633.4KB)
>>Buy this Article
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.