Search ETDs:
New Heuristic And Metaheuristic Approaches Applied To The Multiple-choice Multidimensional Knapsack Problem
Hiremath, Chaitr

2008, Doctor of Philosophy (PhD), Wright State University, Engineering PhD.

The knapsack problem has been used to model various decision making processes. Industrial applications find the need for satisfying additional constraints and these necessities lead to the variants and extensions of knapsack problems which are complex to solve. Heuristic algorithms have been developed by many researchers to solve the variants of knapsack problems. Empirical analysis has been done to compare the performance of these heuristics. Little research has been done to find out why certain algorithms perform well on certain test problems while not so well on other test problems. There has been little work done to gain knowledge of the test problem characteristics and their effects on algorithm performance.

The research focuses on the Multiple-choice Multidimensional Knapsack Problem (MMKP), a complex variant of the knapsack problem. The objectives of the research are fourfold. The first objective is to show how empirical science can lead to theory. The research involves the empirical analysis of current heuristics with respect to problem structure especially constraint correlation and constraint slackness settings. The second objective is to consider the performance traits of heuristic procedures and develop a more diverse set of MMKP test problems considering problem characteristics like the number of variables, number of constraints, constraint correlation, and constraint right-hand side capacities. The third objective is the development of new heuristic approaches for solving the MMKP. This involves examining the existing heuristics against our new test set and using the analysis of the results to help in the development of new heuristic approaches. The fourth objective is to develop improved metaheuristic procedures for the MMKP using the improved heuristic approaches to initialize searches or to improve local search neighborhoods.


Raymond Hill, PhD (Advisor)
James T. Moore, PhD (Committee Member)
Xinhui Zhang, PhD (Committee Member)
Gary Kinney, PhD (Committee Member)
Mateen Rizki, PhD (Committee Member)
252 p.

Recommended Citations

Hide/Show APA Citation

Hiremath, C. (2008). New Heuristic And Metaheuristic Approaches Applied To The Multiple-choice Multidimensional Knapsack Problem. (Electronic Thesis or Dissertation). Retrieved from https://etd.ohiolink.edu/

Hide/Show MLA Citation

Hiremath, Chaitr. "New Heuristic And Metaheuristic Approaches Applied To The Multiple-choice Multidimensional Knapsack Problem." Electronic Thesis or Dissertation. Wright State University, 2008. OhioLINK Electronic Theses and Dissertations Center. 31 Mar 2015.

Hide/Show Chicago Citation

Hiremath, Chaitr "New Heuristic And Metaheuristic Approaches Applied To The Multiple-choice Multidimensional Knapsack Problem." Electronic Thesis or Dissertation. Wright State University, 2008. https://etd.ohiolink.edu/

Files

wright1203960454.pdf (1.81 MB) View|Download