DC FieldValueLanguage
dc.contributor.authorDavidović, Tatjanaen_US
dc.contributor.authorJelić, Slobodanen_US
dc.date.accessioned2024-09-06T09:10:53Z-
dc.date.available2024-09-06T09:10:53Z-
dc.date.issued2024-
dc.identifier.isbn978-3-031-62911-2-
dc.identifier.isbn978-3-031-62912-9-
dc.identifier.issn0302-9743-
dc.identifier.urihttp://researchrepository.mi.sanu.ac.rs/handle/123456789/5347-
dc.description.abstractFor a given undirected graph G=(V,E) with a non-negative weight function w:E→R+ and subsets (formula presented) of V, the Group Steiner Tree (GST) problem consists of constructing a tree T=(VT,ET) with minimal cost, where (formula presented), and T spans at least one node from each of the groups. We develop a VNS-based metaheuristics approach for solving the GST problem. Our main contribution is that we propose a new problem-specific node release strategy that mimics the steps of a VNS-based heuristic. Instead of exploring different neighborhoods by combinatorially enumerating neighboring solutions, as in classical local search, we use a provably good Integer Linear Programming (ILP) formulation to solve a sequence of subproblems of the original problem. Our approach leads to an improvement over the state-of-the-art Gurobi solver both in terms of quality and runtime of the instances available in the literature.en_US
dc.publisherSpringer Linken_US
dc.relation.ispartofseriesLecture Notes in Computer Science (LNCS)en_US
dc.subjectdecomposition strategy | hybrid heuristic | integer programming formulation | metaheuristic methods | subtour eliminationen_US
dc.titleVNS-Based Matheuristic Approach to Group Steiner Tree with Problem-Specific Node Release Strategyen_US
dc.typeConference Paperen_US
dc.relation.conference15th International Conference, MIC 2024, Lorient, France, June 4–7, 2024en_US
dc.relation.publicationMetaheuristics : Proceedings, Part Ien_US
dc.identifier.doi10.1007/978-3-031-62912-9_32-
dc.identifier.scopus2-s2.0-85198020698-
dc.contributor.affiliationComputer Scienceen_US
dc.contributor.affiliationMathematical Institute of the Serbian Academy of Sciences and Artsen_US
dc.relation.firstpage344-
dc.relation.lastpage358-
dc.relation.volume14753-
item.fulltextNo Fulltext-
item.openairetypeConference Paper-
item.grantfulltextnone-
item.cerifentitytypePublications-
item.openairecristypehttp://purl.org/coar/resource_type/c_18cf-
crisitem.author.orcid0000-0001-9561-5339-
Show simple item record

Page view(s)

44
checked on Jan 31, 2025

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.