An Algorithm for the Multidimensional Multiple-Choice Knapsack Problem
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E80-A No.3 pp.582-589
- Publication Date
- 1997/03/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Category
- Systems and Control
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Martin MOSER, Dusan P.JOKANOVIC, Norio SHIRATORI, "An Algorithm for the Multidimensional Multiple-Choice Knapsack Problem" in IEICE TRANSACTIONS on Fundamentals,
vol. E80-A, no. 3, pp. 582-589, March 1997, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e80-a_3_582/_p
Copy
@ARTICLE{e80-a_3_582,
author={Martin MOSER, Dusan P.JOKANOVIC, Norio SHIRATORI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={An Algorithm for the Multidimensional Multiple-Choice Knapsack Problem},
year={1997},
volume={E80-A},
number={3},
pages={582-589},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={March},}
Copy
TY - JOUR
TI - An Algorithm for the Multidimensional Multiple-Choice Knapsack Problem
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 582
EP - 589
AU - Martin MOSER
AU - Dusan P.JOKANOVIC
AU - Norio SHIRATORI
PY - 1997
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E80-A
IS - 3
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - March 1997
AB - 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.
ER -
English
