Publication Date
2008
Document Type
Dissertation
Committee Members
Raymond Hill (Advisor), Gary Kinney (Committee Member), James T. Moore (Committee Member), Mateen Rizki (Committee Member), Xinhui Zhang (Committee Member)
Degree Name
Doctor of Philosophy (PhD)
Abstract
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.
Page Count
252
Department or Program
Ph.D. in Engineering
Year Degree Awarded
2008
Copyright
Copyright 2008, all rights reserved. This open access ETD is published by Wright State University and OhioLINK.
