Skip to Main Content
 

Global Search Box

 
 
 
 

ETD Abstract Container

Abstract Header

New Heuristic And Metaheuristic Approaches Applied To The Multiple-choice Multidimensional Knapsack Problem

Hiremath, Chaitr

Abstract Details

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

Citations

  • Hiremath, C. (2008). New Heuristic And Metaheuristic Approaches Applied To The Multiple-choice Multidimensional Knapsack Problem [Doctoral dissertation, Wright State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=wright1203960454

    APA Style (7th edition)

  • Hiremath, Chaitr. New Heuristic And Metaheuristic Approaches Applied To The Multiple-choice Multidimensional Knapsack Problem. 2008. Wright State University, Doctoral dissertation. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=wright1203960454.

    MLA Style (8th edition)

  • Hiremath, Chaitr. "New Heuristic And Metaheuristic Approaches Applied To The Multiple-choice Multidimensional Knapsack Problem." Doctoral dissertation, Wright State University, 2008. http://rave.ohiolink.edu/etdc/view?acc_num=wright1203960454

    Chicago Manual of Style (17th edition)