Наредни састанак Семинара биће одржан онлајн у уторак, 22.марта 2022. са почетком у 14.15.
Предавач: Слободан Јелић, Josip Juraj Strossmayer University of Osijek
Наслов предавања: GENERAL VARIABLE NEIGHBORHOOD SEARCH APPROACH TO GROUP STEINER TREE PROBLEM
Апстракт: In this paper, we consider the Group Steiner Tree (GST) problem that can be stated as follows: For a given non-negative edge weighted graph G = (V, E), an integer k, and the corresponding family $g_1, \ldots, g_k$ containing non-empty subsets of V called groups, we need to find a minimum cost tree $T = (V_T, E_T)$ where $V_T \subseteq V$ and $E_T\subseteq E$ that spans at least one vertex from each of the groups. Numerous applications of this NP-hard problem initiated researchers to study it from both theoretical and algorithmic aspects. One of the challenges is to provide a good heuristic solution within the reasonable amount of CPU time. We propose the application of metaheuristic framework based on Variable Neighborhood Search (VNS) and related approaches. One of our main objectives is to find a neighborhood structure that ensures efficient implementation. We develop Variable Neighborhood Descend (VND) algorithm that is the main ingredient of several local search approaches.
Experimental evaluation involves comparison of our heuristics to exact approaches based on Integer Linear Programming solvers and other metaheuristic approaches such as genetic algorithm. The obtained results show that the proposed method always outperforms genetic algorithm. Exact method is outperformed in the case of instances with large number of groups.
This is joint work with Luka Matijević and Tatjana Davidović.
Напомена: Због тренутне епидемиолошке ситуације, предавања се могу пратити искључиво на даљину преко линка:
https://miteam.mi.sanu.ac.rs/asset/YoqHWKALRkRTbK9So
За активно учешће на Семинару неопходна је регистрација преко линка:
https://miteam.mi.sanu.ac.rs/asset/xzGqvSp7aWbg8WpYX