Parallel Algorithm for Combinatorial Optimization Problem
Keywords:
MapReduce, Combinatorial Optimization Problem, Knapsack Problem, Metaheuristics.Abstract
Combinatorial optimization problems (COP) are difficult to solve by nature. One of the reasons is because the amount of neighborhood search required to generate high quality solutions based on sequential methods is intractable. In this paper, parallel algorithm for COP such as Knapsack Problem is presented. Knapsack problem arises in different types of resource allocation problems and has many applications in real-world problems. The proposed algorithm is based on MapReduce framework where the workload for neighborhood search is distributed across available computing nodes in the cluster. The design of Map and Reduce phases is proposed based on consecutive runs of MapReduce jobs. The computational results that shows the effect of degree of parallelism on the solution quality are provided.
Downloads
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2024 Journal of Telecommunication, Electronic and Computer Engineering
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)