Parallel Algorithm for Combinatorial Optimization Problem

Authors

  • Narameth Nananukul Sirindhorn International Institute of Technology, Thammasat University, Pathum Thani, Thailand, 12121.

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.

References

Martello, S., Pisinger, P. and Toth, P. 1999. Dynamic Programming and strong bounds for the 0-1 knapsack problem. Manag. Sci., 45:414-424.

Lam, C. 2010. Hadoop in Action. Manning Publications Co.

Fiechter, C.N. 1994. A parallel tabu search algorithm for large traveling salesman problems. Discrete Applied Mathematics, 51(3): 243-267.

Cesari, G. 1996. Divide and conquer strategies for parallel TSP heuristics. Computers and Operations Research, 23(7): 681-694.

Tsutsui, S. and Fujimoto, N. 2010. Parallel Ant Colony Optimization algorithm on a Multi-core Processor. Lecture Notes in Computer Science, 6234(2010): 488-495.

Hoos, H. H. and T. Stutzle. 2005. Stochastic Local Search: Foundations and Applications. Morgan Kaufmann.

Glover, F. and M. Laguna. 1997. Tabu search. Kluwer.

Drexel, A. 1988. A Simulated Annealing Approach to the

Multiconstraint Zero-One Knapsack Problem. Computing, 40:1-8.

Freville, A. and Plateau, G. 1990. Hard 0-1 multiknapsack testproblems for size reduction methods. Investigation Operativa, 1:251-270.

Shi, W. 1979. A branch and bound method for the multiconstraint zero one knapsack problem. J. Opl. Res. Soc., 30:369-378.

Lin, J. and C. Dyer. 2010. Data-Intensive Text Processing with MapReduce. Morgan and Claypool Publishers.

Amazon Elastic MapReduce Developer Guide, API Version 2009-03-31.

Downloads

Published

2017-06-01

How to Cite

Nananukul, N. (2017). Parallel Algorithm for Combinatorial Optimization Problem. Journal of Telecommunication, Electronic and Computer Engineering (JTEC), 9(2-2), 1–5. Retrieved from https://jtec.utem.edu.my/jtec/article/view/2210