Parallel strategies for a multi-criteria GRASP algorithm

This paper proposes different strategies of parallelizing a multi-criteria GRASP (greedy randomized adaptive search problem) algorithm. The parallel GRASP algorithm is applied to the multi-criteria minimum spanning tree problem, which is NP-hard. In this problem, a vector of costs is defined for eac...

Full description

Saved in:
Bibliographic Details
Main Authors: Vianna, D.S., Arroyo, J.E.C., Vieira, P.S., de Azeredo, T.R.
Format: Conference Proceeding
Language:English
Subjects:
Cities and towns
Concurrent computing
Cost function
Design optimization
Large-scale systems
minimum spanning tree
multi-criteria combinatorial optimization
Parallel algorithms
Parallel GRASP algorithm
Search problems
Telecommunication traffic
Testing
Tree graphs
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper proposes different strategies of parallelizing a multi-criteria GRASP (greedy randomized adaptive search problem) algorithm. The parallel GRASP algorithm is applied to the multi-criteria minimum spanning tree problem, which is NP-hard. In this problem, a vector of costs is defined for each edge of the graph and the goal is to find all the efficient or Pareto optimal spanning trees (solutions). Each process finds a subset of efficient solutions. These subsets are joined using different strategies to obtain the final set of efficient solutions. The multi-criteria GRASP algorithm with the different parallel strategies are tested on complete graphs with n = 20, 30 and 50 nodes and r = 2 and 3 criteria. The computational results show that the proposed parallel algorithms reduce the execution time and the results obtained by the sequential version were improved.
ISSN:1522-4902
2691-0632
DOI:10.1109/SCCC.2005.1587873