說明 
134 p 
附註 
Source: Dissertation Abstracts International, Volume: 7005, Section: B, page: 3152 

Adviser: Jose A. Sepulveda 

Thesis (Ph.D.)University of Central Florida, 2009 

This dissertation introduces new heuristic methods for the 01 multidimensional knapsack problem (01 MKP). 01 MKP can be informally stated as the problem of packing items into a knapsack while staying within the limits of different constraints (dimensions). Each item has a profit level assigned to it. They can be, for instance, the maximum weight that can be carried, the maximum available volume, or the maximum amount that can be afforded for the items. One main assumption is that we have only one item of each type, hence the problem is binary (01). The single dimensional version of the 01 MKP is the unidimensional single knapsack problem which can be solved in pseudopolynomial time. However the 01 MKP is a strongly NPHard problem 

Reduced cost values are rarely used resources in 01 MKP heuristics; using reduced cost information we introduce several new heuristics and also some improvements to past heuristics. We introduce two new ordering strategies, decision variable importance (DVI) and reduced cost based ordering (RCBO). We also introduce a new greedy heuristic concept which we call the sliding concept" and a subbranch of the "sliding concept" which we call "sliding enumeration". We again use the reduced cost values within the sliding enumeration heuristic 

RCBO is a brand new ordering strategy which proved useful in several methods such as improving Pirkul's MKHEUR, a triangular distribution based probabilistic approach, and our own sliding enumeration 

We show how Pirkul's shadow price based ordering strategy fails to order the partial variables. We present a possible fix to this problem since there tends to be a high number of partial variables in hard problems. Therefore, this insight will help future researchers solve hard problems with more success 

Even though sliding enumeration is a trivial method it found optima in less than a few seconds for most of our problems. We present different levels of sliding enumeration and discuss potential improvements to the method 

Finally, we also show that in metaheuristic approaches such as Drexl's simulated annealing where random numbers are abundantly used, it would be better to use better designed probability distributions instead of random numbers 

School code: 0705 
Host Item 
Dissertation Abstracts International 7005B

主題 
Engineering, Industrial


Operations Research


0546


0796

Alt Author 
University of Central Florida

