This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/129592
Description
Title
Generalized Group Steiner Trees
Author(s)
Baizhan, Darkhan
Issue Date
2025-04-28
Director of Research (if dissertation) or Advisor (if thesis)
Vogiatzis, Chrysafis
Department of Study
Industrial&Enterprise Sys Eng
Discipline
Industrial Engineering
Degree Granting Institution
University of Illinois Urbana-Champaign
Degree Name
M.S.
Degree Level
Thesis
Keyword(s)
Combinatorial Optimization
Integer Programming
Group Steiner Tree Problem
Generalized Group Steiner Tree Problem
Abstract
In this work, we investigate a recent extension to the well-known combinatorial optimization instance Steiner Tree in graphs, referred to as the Generalized Group Steiner tree problem. In this variant, we aim to identify a tree of minimum total cost that spans a given set of groups and subject to a series of logical relationships among these groups. First, essential background and notation for Steiner Tree problems are first provided, including discussions on practical applications of Steiner Trees, Group Steiner Trees, and Generalized Group Steiner Trees.
Next we formulated integer programming models incorporating diverse logical constraints, including AND, OR, XOR, XNOR, NAND, and IF/THEN. To quantify the additional computational effort imposed by these logical relationships, comprehensive integer programming models utilizing an extended subtour elimination formulation were developed and solved using advanced optimization solvers. Extensive computational experiments were conducted on synthetic scale-free graphs generated with theBarab´asi-Albert model, complemented by community structures identified using the Girvan-Newman algorithm. The experimental outcomes clearly illustrate a significant rise in computational complexity when logical constraints are integrated, with IF/THEN constraints demonstrating the most pronounced effect on solver runtimes. Additionally, the results underscore a marked dependency of computational performance on the underlying network topology. These insights substantially enhance the comprehension of the computational complexities inherent in the Generalized Group Steiner Tree Problem (GGSTP). Furthermore, the findings hold considerable practical implications, informing the design and optimization strategies for large-scale network applications, and lay a robust groundwork for future exploration into heuristic algorithms and real-world implementation scenarios.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
