Семинар за рачунарство и примењену математику, 22. март 2022.

• 21. Март, 2022
• Коментари (0)

Наредни састанак Семинара биће одржан онлајн у уторак, 22. марта 2022. са почетком у 14.15.

Предавач: Слободан Јелић, Јосип Јурај Строссмаѕер Университѕ оф Осијек

Наслов предавања: 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 nitiated 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