Document Type : Original Article

Authors

• Saeed Mirpour Marzuni ¹
• Javad Vahidi ²

¹ Department of Electrical and Computer Engineering, University of Science and Technology of Mazandaran, Behshahr, Iran

² Iran University of Science and Technology

Abstract

NP-hard optimization problems are computationally challenging tasks that require significant resources to solve, particularly as problem sizes increase. In this paper, we introduce a novel framework, GiraDP, which converts dynamic programming problems into graphs and solves these large-scale graphs efficiently. GiraDP addresses NP-hard optimization problems by leveraging advanced graph processing techniques. The framework utilizes Giraph and Hadoop in its architecture to manage extensive datasets and complex computations. It generates input data for Giraph and identifies active vertices that correspond to sub-problems within the larger problem. Our experiments include scenarios with 20, 40, and 60 items, across varying knapsack capacities. The results indicate that while the serial algorithm performs best at low capacities, it fails to handle larger instances due to memory limitations, resulting in heap space errors. In contrast, GiraDP demonstrates superior efficiency and scalability for high capacities and large item sets. The MPI-based approach also shows improved performance over the serial algorithm for larger problems, although it does not match the efficiency of GiraDP. These findings underscore the importance of distributed computing solutions for large-scale optimization problems.

Keywords

• Giraph
• Dynamic Programing
• Hadoop
• Knapsack Problem