Knapsack Problems; Methods, Models and Applications

Abstract

Knapsack problem (KP) has broad applications in different fields such as machine scheduling, space allocation, and asset optimization. Meanwhile, it is a hard problem due to its computational complexity, but numerous solution approaches have been developed for a variety of KP. In this dissertation, an extensive literature review is first provided. Then, the research focuses on methods, models, and applications for two variations of Knapsack problem: Multiple Knapsack Problem with Assignment Restrictions (MKAR) and Stochastic Knapsack Problem with Penalty Cost (SKPPC).

A new procedure, Largest Unutilized Capacity First Algorithm (LUCF) is developed and tested on MKAR along with other assignment procedures available in the literature. It is concluded that LUCF performs very well and it returns the best initial feasible solution among all types of greedy algorithms for the solution of the MKAR. After the generation of initial feasible solutions, a tabu-search procedure is implemented to generate improved solutions. Three versions of intensification procedures are implemented within the tabu search procedure. Experimental results show significant improvement over the initial solution quality with the tabu search procedure. That is, this approach yields a high percentage of utilization for all combinations of problems, based on the initial solution provided by LUCF.

For SKPPC, for each item of the knapsack, there are several possible processing times, each with certain probability of selection. For a given knapsack capacity, a strategy is developed to assign the optimal number of items to each the knapsack. Mathematical formulations are provided for both single knapsack and m-knapsack cases. The objective value function for the single knapsack problem exhibits a convex property, which leads to an optimal strategy to assign the number of items. For the m-knapsack case, the processing time of each item will be revealed after pre-scan operations. LUCF heuristic is combined here to obtain good solutions. This approach is finally adapted to the package security inspection problem. We discuss how one can determine the optimal number of items in each knapsack and the optimal number of operators needed for inspection with the objective of maximizing operator utilization and throughput.