Parallel strategies for a multi-criteria GRASP algorithm

Author

Vianna, Dalessandro Soares ; Arroyo, José Elias Claudio ; Vieira, Pedro Sampaio ; De Azeredo, Thiago Ribeiro

Author_Institution

Nucleo de Pesquisa e Desenvolvimento em Informatica, Univ. Candido Mendes, Rio de Janiero, Brazil

fYear

2005

fDate

7-11 Nov. 2005

Abstract

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.

Keywords

Pareto optimisation; adaptive systems; computational complexity; greedy algorithms; parallel algorithms; randomised algorithms; tree searching; trees (electrical); NP-hard problem; Pareto optimal spanning trees; combinatorial optimization; graph edges; greedy randomized adaptive search problem; multicriteria GRASP algorithm; multicriteria minimum spanning tree problem; parallel algorithm; Cities and towns; Concurrent computing; Cost function; Design optimization; Large-scale systems; Parallel algorithms; Search problems; Telecommunication traffic; Testing; Tree graphs; Parallel GRASP algorithm; minimum spanning tree.; multi-criteria combinatorial optimization;

fLanguage

English

Publisher

ieee

Conference_Titel

Chilean Computer Science Society, 2005. SCCC 2005. 25th International Conference of the

ISSN

1522-4902

Print_ISBN

0-7695-2491-5

Type

conf

DOI

10.1109/SCCC.2005.1587873

Filename

1587873