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' ).
