Title :
A New Heuristic for Solving the Multichoice Multidimensional Knapsack Problem
Author :
Parra-Hernández, Rafael ; Dimopoulos, Nikitas J.
Author_Institution :
Dept. of Electr. & Comput. Eng., Univ. of Victoria, BC, Canada
Abstract :
A new heuristic for solving the multichoice multidimensional knapsack problem (MMKP) is presented in this paper. The MMKP is first reduced to a multidimensional knapsack problem (MKP). A linear programming relaxation of the resulting MKP is solved, and a series of new values for the variables is computed. These values, pseudo-utility values, and resource value coefficients computed as well, are used in order to obtain a feasible solution for the original MMKP. Finally, the quality of the feasible solution is improved using the pseudo-utility values and the coefficient values of the objective function. Numerical results show that the performance of this approach is superior to that of previous techniques.
Keywords :
combinatorial mathematics; knapsack problems; linear programming; optimisation; combinatorial mathematics; linear programming; multichoice multidimensional knapsack problem; pseudo utility values; resource value coefficient; Degradation; Helium; Land mobile radio cellular systems; Linear programming; Mathematical model; Multicast protocols; Multidimensional systems; Multimedia systems; Quality of service; Resource management; Heuristics; multichoice multidimensional knapsack problem (MMKP);
Journal_Title :
Systems, Man and Cybernetics, Part A: Systems and Humans, IEEE Transactions on
DOI :
10.1109/TSMCA.2005.851140