On efficient techniques for NP hard problems

Abstract

Many real-world operational level optimization problems contain several newlinechallenges: the problem sizes are often very large and frequently the problems are newlinetime-sensitive in nature. Hence the effectiveness of solution depends on both its newlinequality and speed at which it can be generated. The problems are often NP-Hard newlineand therefore it is unlikely that one finds fast algorithms which will guaranty the newlinesolutions leading to optimality. newlineIn this dissertation, two different approaches namely heuristic and metaheuristic newlineare proposed for solving different Multidimensional Knapsack Problems newlineand Graph Theoretical Optimization Problems respectively. The goals of this research are twofold. newlineThe first goal is to design heuristics for Mulidimensional Knapsack problems, newlineGeneralized Assignment Problems, Multi-choice Multidimensional Knapsack newlineProblems and Multi-demand Multidimensional Knapsack Problems. The research newlineinvolves the theoretical analysis of the heuristic like, worst-case bound and convergence newlineanalysis through probabilistic approach with respect to problem structure newlineand comparison of the performance of proposed heuristcs with existing approaches newlineto establish the better quality of our proposed heuristics. newlineThe worst case analysis of Multidimensional Knapsack problems is grounded newlineupon the operator based on Number Theory. The Reciprocal of the value of the newlineharmonic series generated by the intercept coefficients act as the upper bound for newlinethe ratio of heuristic solution to the optimal solution. This fact has been proved for all designed algorithms in each chapter. This bound together with the exponential newlinedecrease of the successive difference between iterates ensure the convergence. newlineThe sufficient condition for existence of optimal solutions for the DPH newlinehas also been derived for each algorithm proposed. This has lent confidence to newlinefind the optimal solutions or near optimal solutions for a series of test / real time newline/ benchmark problems of bigger sizes. These heuristic has been tested for 999 newlineproblems of sizes upto 10000 obtained