Solving the Generalized Steiner Problem in edge-survivable networks
The Generalized Steiner Problem with Edge-Connectivity constraints (GSP-EC) consists of computing the minimal cost subnetwork of a given feasible network where some pairs of nodes must satisfy edge-connectivity requirements. It can be applied in the design of communications networks where connection...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | report |
| Published: |
2011
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/20.500.12008/3461 |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1868890216591261696 |
|---|---|
| author | Sartor, Pablo |
| author2 | Robledo, Franco |
| author2_role | author |
| author_browse | Robledo, Franco Sartor, Pablo |
| author_facet | Sartor, Pablo Robledo, Franco |
| author_role | author |
| collection | COLIBRI |
| dc.creator.none.fl_str_mv | Sartor, Pablo Robledo, Franco |
| dc.date.none.fl_str_mv | 2011 2014-12-02T16:06:24Z 2014-12-02T16:06:24Z 20141202 |
| dc.format.none.fl_str_mv | 17 p. application/pdf |
| dc.identifier.none.fl_str_mv | SARTOR, P., ROBLEDO, F. "Solving the Generalized Steiner Problem in edge-survivable networks". Reportes Técnicos 11-09. UR. FI – INCO, 2011. 0797-6410 http://hdl.handle.net/20.500.12008/3461 |
| dc.language.none.fl_str_mv | in |
| dc.publisher.none.fl_str_mv | UR. FI – INCO. |
| dc.relation.none.fl_str_mv | Reportes Técnicos 11-09 |
| dc.rights.none.fl_str_mv | info:eu-repo/semantics/openAccess Licencia Creative Commons Atribución – No Comercial – Sin Derivadas (CC BY-NC-ND 4.0) |
| dc.source.none.fl_str_mv | reponame:COLIBRI instname:Universidad de la República instacron:Universidad de la República |
| dc.subject.none.fl_str_mv | Network design Edge-connectivity Survivability Steiner problems Metaheuristics GRASP |
| dc.title.none.fl_str_mv | Solving the Generalized Steiner Problem in edge-survivable networks |
| dc.type.none.fl_str_mv | Reporte técnico info:eu-repo/semantics/report info:eu-repo/semantics/publishedVersion |
| description | The Generalized Steiner Problem with Edge-Connectivity constraints (GSP-EC) consists of computing the minimal cost subnetwork of a given feasible network where some pairs of nodes must satisfy edge-connectivity requirements. It can be applied in the design of communications networks where connection lines can fail and is known to be an NP-Complete problem. In this paper we introduce an algorithm based on GRASP (Greedy Randomized Adaptive Search Procedure), a combinatorial optimization metaheuristic that has proven to be very effective for such problems. Promising results are obtained when testing the algorithm over a set of heterogeneous network topologies and connectivity requirements; in all cases with known optimal cost, optimal or near-optimal solutions are found. |
| eu_rights_str_mv | openAccess |
| format | report |
| id | anni_e2d393c581da3bc11ced37343d201087 |
| identifier_str_mv | SARTOR, P., ROBLEDO, F. "Solving the Generalized Steiner Problem in edge-survivable networks". Reportes Técnicos 11-09. UR. FI – INCO, 2011. 0797-6410 |
| instacron_str | Universidad de la República |
| institution | Universidad de la República |
| instname_str | Universidad de la República |
| language_invalid_str_mv | in |
| network_acronym_str | anni |
| network_name_str | oai-lr-anni |
| oai_identifier_str | oai:colibri.udelar.edu.uy:20.500.12008/3461 |
| publishDate | 2011 |
| publishDateSort | 2011 |
| publisher.none.fl_str_mv | UR. FI – INCO. |
| reponame_str | COLIBRI |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| rights_invalid_str_mv | Licencia Creative Commons Atribución – No Comercial – Sin Derivadas (CC BY-NC-ND 4.0) |
| spelling | Solving the Generalized Steiner Problem in edge-survivable networksSartor, PabloRobledo, FrancoNetwork designEdge-connectivitySurvivabilitySteiner problemsMetaheuristicsGRASPThe Generalized Steiner Problem with Edge-Connectivity constraints (GSP-EC) consists of computing the minimal cost subnetwork of a given feasible network where some pairs of nodes must satisfy edge-connectivity requirements. It can be applied in the design of communications networks where connection lines can fail and is known to be an NP-Complete problem. In this paper we introduce an algorithm based on GRASP (Greedy Randomized Adaptive Search Procedure), a combinatorial optimization metaheuristic that has proven to be very effective for such problems. Promising results are obtained when testing the algorithm over a set of heterogeneous network topologies and connectivity requirements; in all cases with known optimal cost, optimal or near-optimal solutions are found.UR. FI – INCO.2014-12-02T16:06:24Z2014-12-02T16:06:24Z201120141202Reporte técnicoinfo:eu-repo/semantics/reportinfo:eu-repo/semantics/publishedVersion17 p.application/pdfSARTOR, P., ROBLEDO, F. "Solving the Generalized Steiner Problem in edge-survivable networks". Reportes Técnicos 11-09. UR. FI – INCO, 2011.0797-6410http://hdl.handle.net/20.500.12008/3461reponame:COLIBRIinstname:Universidad de la Repúblicainstacron:Universidad de la RepúblicainReportes Técnicos 11-09Las obras depositadas en el Repositorio se rigen por la Ordenanza de los Derechos de la Propiedad Intelectual de la Universidad De La República. (Res. Nº 91 de C.D.C. de 8/III/1994 – D.O. 7/IV/1994) y por la Ordenanza del Repositorio Abierto de la Universidad de la República (Res. Nº 16 de C.D.C. de 07/10/2014)info:eu-repo/semantics/openAccessLicencia Creative Commons Atribución – No Comercial – Sin Derivadas (CC BY-NC-ND 4.0)oai:colibri.udelar.edu.uy:20.500.12008/34612026-04-14T10:16:11Z |
| spellingShingle | Solving the Generalized Steiner Problem in edge-survivable networks Sartor, Pablo Network design Edge-connectivity Survivability Steiner problems Metaheuristics GRASP |
| status_str | publishedVersion |
| title | Solving the Generalized Steiner Problem in edge-survivable networks |
| title_full | Solving the Generalized Steiner Problem in edge-survivable networks |
| title_fullStr | Solving the Generalized Steiner Problem in edge-survivable networks |
| title_full_unstemmed | Solving the Generalized Steiner Problem in edge-survivable networks |
| title_short | Solving the Generalized Steiner Problem in edge-survivable networks |
| title_sort | Solving the Generalized Steiner Problem in edge-survivable networks |
| topic | Network design Edge-connectivity Survivability Steiner problems Metaheuristics GRASP |
| url | http://hdl.handle.net/20.500.12008/3461 |