Parallel algorithm of heuristic for the multiple-choise multi-dimension knapsack problem

Abstract

Multiple-Choice Multi-Dimension Knapsack Problem (MMKP) is a variant of the classical 0-1 Knapsack Problem. It has a knapsack with a multidimensional capacity constraint and groups of items where each item having a utility value and a multidimensional weight constraint. The knapsack is to be filled by picking up exactly one item from each group. The problem is to maximize the total value of the items in the knapsack but not exceeding the knapsack capacity. MMKP is an NP-Hard problem and its exact solution is not suitable for real time decision making applications. Therefore heuristic based approximation algorithms are developed. Khan developed a heuristic, HEU, which achieves 93% of the optimal solution value. Later Akbar et al. presented MHEU, a modification ofHEU, achieving 96% of the optimal value with a time complexity ofO(mn'I'), where n is the number of groups, I is the number of items in each group and m is the number of resource constraints. But, these heuristic algorithms do not scale better for larger systems. In this thesis, a new sequential heuristic algorithm is developed by modifying M-HEU to some extent that would be parallelized. Later a parallel heuristic algorithm is introduced that is the parallel version of the new sequential heuristic algorithm. And the new sequential heuristic algorithm is used to compare the performance of the parallel heuristic algorithm. Experimental result shows the new heuristic algorithm achieves 94.5% of the optimal value. The time complexity of the parallel algorithm is O(log nl(log n + log m + log log z)) with O(n log nl(log n + 1m)) number of operations in Concurrent Read Concurrent Write (CRCW) PRAM model, i.e., the required number of processors is O((n log n + nlm )/(log n + log m + log log I)). This also means that we have a sequential heuristic algorithm running in O(n log nl(log n + 1m)) time which seems to be remarkable since M-HEU, a celebrated sequential heuristic, although achieves 96% of optimal value, takes the time complexity of O(mn2l' ).