Please use this identifier to cite or link to this item:
Title: The 0 -1 multiple knapsack problem
Authors: Shamakhai, Hayat Abdullah
Keywords: generalized assignment problem;assignment problem;knapsack problem;multiple knapsack problem;branch and bound algorithm;bound and bound algorithm;transportation problem;multiple assignment problem;adapted transportation problem;vogel approximation method;group role assignment problem.
Issue Date: 31-May-2017
Abstract: In operation research, the Multiple Knapsack Problem (MKP) is classified as a combinatorial optimization problem. It is a particular case of the Generalized Assignment Problem. The MKP has been applied to many applications in naval as well as financial management. There are several methods to solve the Knapsack Problem (KP) and Multiple Knapsack Problem (MKP); in particular the Bound and Bound Algorithm (B&B). The bound and bound method is a modification of the Branch and Bound Algorithm which is defined as a particular tree-search technique for the integer linear programming. It has been used to obtain an optimal solution. In this research, we provide a new approach called the Adapted Transportation Algorithm (ATA) to solve the KP and MKP. The solution results of these methods are presented in this thesis. The Adapted Transportation Algorithm is applied to solve the Multiple Knapsack Problem where the unit profit of the items is dependent on the knapsack. In addition, we will show the link between the Multiple Knapsack Problem (MKP) and the multiple Assignment Problem (MAP). These results open a new field of research in order to solve KP and MKP by using the algorithms developed in transportation.
Appears in Collections:Computational Sciences - Master's theses
Master's Theses

Files in This Item:
File Description SizeFormat 
thesisFINAL-Hayat Shamakhai-3 final correction (1).pdf1.74 MBAdobe PDFThumbnail

Items in LU|ZONE|UL are protected by copyright, with all rights reserved, unless otherwise indicated.