Knapsack problem and its applications

Abstract

This dissertation examines different types of the Knapsack Problem. Mainly the focus is on the 0-1 Knapsack Problem, the 0-1 Multidimensional Knapsack Problem, the Bounded Knapsack Problem and the Unbounded Knapsack Problem. For the 0-1 Knapsack Problem, several relaxations that can be applied on the model and bounds are described. Then algorithms such as the greedy algorithm and some other approximate algorithms and some Branch and Bound methods are stated. For the case when the number of items is large, a reduction algorithm can be applied and thus the core problem is defined. Also a heuristic that improves exponentially with the problem size in finding a solution is described. Modelling for this type of Knapsack Problem is also done by MATLAB. Again for the 0-1 Multidimensional Knapsack Problem, several relaxations can be applied on the model. A Branch and Bound method is also given to solve this problem. This type of model can be reformulated, which many in the literature refer to it as the Multiknapsack Problem. Some asymptotic results are then given which show what happens to the optimal solution value as the sample size increases. The Bounded Knapsack Problem is then described and a way of transforming it to the 0-1 Knapsack Problem is given. Some algorithms such as the greedy and a minimal algorithm are presented to solve this problem without any transformation. Finally, the Unbounded Knapsack Problem is analysed and an approximate algorithm to solve it is described. Furthermore, some dominance relations between the item types are discussed. Then this Knapsack Problem is applied to two real life situations. First it is used to obtain an optimal time allocation for undergraduate students in their final year of the course. The Knapsack Problem is a helpful model that is utilised in order to maximize the total reward available. Then it is also used in finding an optimal investment throughout a number of bonds. The Knapsack Problem is the tool used in finding how much an investor must invest in each bond in order to maximize the annual returns. Modelling is done by use of LINGO.