You are here
NEW HEURISTICS FOR THE 01 MULTIDIMENSIONAL KNAPSACK PROBLEMS
 Date Issued:
 2009
 Abstract/Description:
 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.
Title:  NEW HEURISTICS FOR THE 01 MULTIDIMENSIONAL KNAPSACK PROBLEMS. 
33 views
10 downloads 

Name(s): 
Akin, Haluk, Author Sepulveda, Jose, Committee Chair University of Central Florida, Degree Grantor 

Type of Resource:  text  
Date Issued:  2009  
Publisher:  University of Central Florida  
Language(s):  English  
Abstract/Description:  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.  
Identifier:  CFE0002633 (IID), ucf:48195 (fedora)  
Note(s): 
20090501 Ph.D. Engineering and Computer Science, Department of Industrial Engineering and Management Systems Doctorate This record was generated from author submitted information. 

Subject(s): 
01 multidimensional knapsack problems opertations research binary optimization 

Persistent Link to This Record:  http://purl.flvc.org/ucf/fd/CFE0002633  
Restrictions on Access:  public  
Host Institution:  UCF 