Abstract
The 0-1 Knapsack Problem is a combinatorial optimization problem that can be described as follows. Given a set of items with weights and values and a knapsack with a certain capacity, find a subset of the items that fit in the knapsack and produce a maximum profit (sum of values). The 0-1 Knapsack Problem has many applications including the bin packing and the rod cutting problems. In this project, an enhanced branch-and-bound algorithm is developed for the 0-1 Knapsack problem, based on the history utilization technique proposed by Shobaki and Jamal for the Sequential Ordering Problem. The history utilization algorithm stores information about previously generated sub-problems in a history table and uses that information to accelerate the processing of new sub-problems. Experimental results are reported for various synthesized instances ranging in size from 50 to 1000. The history-based breadth-first search algorithm performed 98% better than a breadth-first search strategy without the history information. It successfully solved many instances that timed out with the breadth-first search algorithm without history. The project also involved implementing a parallel (multi-threaded) version of the algorithm that was run on a multi-core system. The experimental results show that running the parallel version of the algorithm on a quad-core machine gives a speedup of up to 35% compared to the single threaded version.