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!
cited_by
cites
container_end_page
container_issue
container_start_page 7 pp.
container_title
container_volume
creator Vianna, D.S.
Arroyo, J.E.C.
Vieira, P.S.
de Azeredo, T.R.
description 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.
doi_str_mv 10.1109/SCCC.2005.1587873
format conference_proceeding
fullrecord <record><control><sourceid>ieee_6IE</sourceid><recordid>TN_cdi_ieee_primary_1587873</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><ieee_id>1587873</ieee_id><sourcerecordid>1587873</sourcerecordid><originalsourceid>FETCH-LOGICAL-i218t-6fd01b87939f2ee14da18998e4ad8b385ca41885d7a37f8248c2377e1e3025a93</originalsourceid><addsrcrecordid>eNotj01Lw0AQQBc_wLb6A8TL_oHEndnd7OyxBK1CwWL1XKbJpK4kVDbx4L9XsKcH7_DgKXULpgQw8X5b13WJxvgSPAUK9kzNsIpQmMriuZqbUEWPLoK_UDPwiIWLBq_UfBw_jUGDEWaKNpy576XX45R5kkOSUXfHrFkP3_2UiianSXJivXpdbjea-8Pxz3wM1-qy436UmxMX6v3x4a1-KtYvq-d6uS4SAk1F1bUG9hSijR2KgGsZKEYSxy3tLfmGHRD5NrANHaGjBm0IAmINeo52oe7-u0lEdl85DZx_dqdj-wsyMEbi</addsrcrecordid><sourcetype>Publisher</sourcetype><iscdi>true</iscdi><recordtype>conference_proceeding</recordtype></control><display><type>conference_proceeding</type><title>Parallel strategies for a multi-criteria GRASP algorithm</title><source>IEEE Electronic Library (IEL) Conference Proceedings</source><creator>Vianna, D.S. ; Arroyo, J.E.C. ; Vieira, P.S. ; de Azeredo, T.R.</creator><creatorcontrib>Vianna, D.S. ; Arroyo, J.E.C. ; Vieira, P.S. ; de Azeredo, T.R.</creatorcontrib><description>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.</description><identifier>ISSN: 1522-4902</identifier><identifier>ISBN: 0769524915</identifier><identifier>ISBN: 9780769524917</identifier><identifier>EISSN: 2691-0632</identifier><identifier>DOI: 10.1109/SCCC.2005.1587873</identifier><language>eng</language><publisher>IEEE</publisher><subject>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</subject><ispartof>XXV International Conference of the Chilean Computer Science Society (SCCC'05), 2005, p.7 pp.</ispartof><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://ieeexplore.ieee.org/document/1587873$$EHTML$$P50$$Gieee$$H</linktohtml><link.rule.ids>309,310,780,784,789,790,2056,4048,4049,27924,54554,54919,54931</link.rule.ids><linktorsrc>$$Uhttps://ieeexplore.ieee.org/document/1587873$$EView_record_in_IEEE$$FView_record_in_$$GIEEE</linktorsrc></links><search><creatorcontrib>Vianna, D.S.</creatorcontrib><creatorcontrib>Arroyo, J.E.C.</creatorcontrib><creatorcontrib>Vieira, P.S.</creatorcontrib><creatorcontrib>de Azeredo, T.R.</creatorcontrib><title>Parallel strategies for a multi-criteria GRASP algorithm</title><title>XXV International Conference of the Chilean Computer Science Society (SCCC'05)</title><addtitle>SCCC</addtitle><description>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.</description><subject>Cities and towns</subject><subject>Concurrent computing</subject><subject>Cost function</subject><subject>Design optimization</subject><subject>Large-scale systems</subject><subject>minimum spanning tree</subject><subject>multi-criteria combinatorial optimization</subject><subject>Parallel algorithms</subject><subject>Parallel GRASP algorithm</subject><subject>Search problems</subject><subject>Telecommunication traffic</subject><subject>Testing</subject><subject>Tree graphs</subject><issn>1522-4902</issn><issn>2691-0632</issn><isbn>0769524915</isbn><isbn>9780769524917</isbn><fulltext>true</fulltext><rsrctype>conference_proceeding</rsrctype><creationdate>2005</creationdate><recordtype>conference_proceeding</recordtype><sourceid>6IE</sourceid><recordid>eNotj01Lw0AQQBc_wLb6A8TL_oHEndnd7OyxBK1CwWL1XKbJpK4kVDbx4L9XsKcH7_DgKXULpgQw8X5b13WJxvgSPAUK9kzNsIpQmMriuZqbUEWPLoK_UDPwiIWLBq_UfBw_jUGDEWaKNpy576XX45R5kkOSUXfHrFkP3_2UiianSXJivXpdbjea-8Pxz3wM1-qy436UmxMX6v3x4a1-KtYvq-d6uS4SAk1F1bUG9hSijR2KgGsZKEYSxy3tLfmGHRD5NrANHaGjBm0IAmINeo52oe7-u0lEdl85DZx_dqdj-wsyMEbi</recordid><startdate>2005</startdate><enddate>2005</enddate><creator>Vianna, D.S.</creator><creator>Arroyo, J.E.C.</creator><creator>Vieira, P.S.</creator><creator>de Azeredo, T.R.</creator><general>IEEE</general><scope>6IE</scope><scope>6IL</scope><scope>CBEJK</scope><scope>RIE</scope><scope>RIL</scope></search><sort><creationdate>2005</creationdate><title>Parallel strategies for a multi-criteria GRASP algorithm</title><author>Vianna, D.S. ; Arroyo, J.E.C. ; Vieira, P.S. ; de Azeredo, T.R.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-i218t-6fd01b87939f2ee14da18998e4ad8b385ca41885d7a37f8248c2377e1e3025a93</frbrgroupid><rsrctype>conference_proceedings</rsrctype><prefilter>conference_proceedings</prefilter><language>eng</language><creationdate>2005</creationdate><topic>Cities and towns</topic><topic>Concurrent computing</topic><topic>Cost function</topic><topic>Design optimization</topic><topic>Large-scale systems</topic><topic>minimum spanning tree</topic><topic>multi-criteria combinatorial optimization</topic><topic>Parallel algorithms</topic><topic>Parallel GRASP algorithm</topic><topic>Search problems</topic><topic>Telecommunication traffic</topic><topic>Testing</topic><topic>Tree graphs</topic><toplevel>online_resources</toplevel><creatorcontrib>Vianna, D.S.</creatorcontrib><creatorcontrib>Arroyo, J.E.C.</creatorcontrib><creatorcontrib>Vieira, P.S.</creatorcontrib><creatorcontrib>de Azeredo, T.R.</creatorcontrib><collection>IEEE Electronic Library (IEL) Conference Proceedings</collection><collection>IEEE Proceedings Order Plan All Online (POP All Online) 1998-present by volume</collection><collection>IEEE Xplore All Conference Proceedings</collection><collection>IEEE Xplore</collection><collection>IEEE Proceedings Order Plans (POP All) 1998-Present</collection></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext_linktorsrc</fulltext></delivery><addata><au>Vianna, D.S.</au><au>Arroyo, J.E.C.</au><au>Vieira, P.S.</au><au>de Azeredo, T.R.</au><format>book</format><genre>proceeding</genre><ristype>CONF</ristype><atitle>Parallel strategies for a multi-criteria GRASP algorithm</atitle><btitle>XXV International Conference of the Chilean Computer Science Society (SCCC'05)</btitle><stitle>SCCC</stitle><date>2005</date><risdate>2005</risdate><spage>7 pp.</spage><pages>7 pp.-</pages><issn>1522-4902</issn><eissn>2691-0632</eissn><isbn>0769524915</isbn><isbn>9780769524917</isbn><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.</abstract><pub>IEEE</pub><doi>10.1109/SCCC.2005.1587873</doi><oa>free_for_read</oa></addata></record>
fulltext fulltext_linktorsrc
identifier ISSN: 1522-4902
ispartof XXV International Conference of the Chilean Computer Science Society (SCCC'05), 2005, p.7 pp.
issn 1522-4902
2691-0632
language eng
recordid cdi_ieee_primary_1587873
source IEEE Electronic Library (IEL) Conference Proceedings
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
title Parallel strategies for a multi-criteria GRASP algorithm
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-12T23%3A38%3A06IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-ieee_6IE&rft_val_fmt=info:ofi/fmt:kev:mtx:book&rft.genre=proceeding&rft.atitle=Parallel%20strategies%20for%20a%20multi-criteria%20GRASP%20algorithm&rft.btitle=XXV%20International%20Conference%20of%20the%20Chilean%20Computer%20Science%20Society%20(SCCC'05)&rft.au=Vianna,%20D.S.&rft.date=2005&rft.spage=7%20pp.&rft.pages=7%20pp.-&rft.issn=1522-4902&rft.eissn=2691-0632&rft.isbn=0769524915&rft.isbn_list=9780769524917&rft_id=info:doi/10.1109/SCCC.2005.1587873&rft_dat=%3Cieee_6IE%3E1587873%3C/ieee_6IE%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-i218t-6fd01b87939f2ee14da18998e4ad8b385ca41885d7a37f8248c2377e1e3025a93%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rft_ieee_id=1587873&rfr_iscdi=true