Enhancing computational efficiency in solving Knapsack problem: insights from algorithmic parallelization and optimization

Abstract

The Knapsack problem is a combinatorial optimization problem whose exact solution using exhaustive search method is impractical. Hence, the application of approximate algorithms is usually considered when encountering this optimization problem. This study optimized some approximate algorithms: greedy, dynamic programming, and branch-and-bound for the Knapsack problem with specific objectives of evaluating their time and program complexity, comparing efficiencies, and enhancing performance. Our methodology involved utilizing advanced Parallelization techniques to accelerate the implementation of loop-based optimization algorithms by distributing tasks across multiple processing units concurrently. This simultaneous execution minimized computational time, enhanced overall efficiency, and improved scalability, enabling effective resolution of large-scale optimization challenges. Additionally, coefficients for the Knapsack model were generated using a random number generation algorithm. Through analysis and experimental runs using Halstead metrics and time complexity measures, significant improvements in the enhanced algorithms compared to classical approaches were revealed, particularly in terms of program complexity and computational speed. Notably, the enhanced algorithms demonstrated superior time complexity across varying input sizes, indicating their potential as more efficient solutions for the Knapsack Problem. This research contributes to advancing Theoretical Computer Science by offering a new computational approach for tackling intricate knapsack-model-based problems, thereby expanding the toolkit for addressing real world challenges across diverse application areas.

Received: 03 June 2024

Accepted: 12 July 2024

Published: 12 August 2024