Generalized Group Steiner Trees

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.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Industrial Engineering

Grantor

University of Illinois Urbana-Champaign

Year dc:date

2025

Author dc:creator

• Baizhan, Darkhan

Contributors dc:contributor

• Vogiatzis, Chrysafis

• Combinatorial Optimization
• Integer Programming
• Group Steiner Tree Problem
• Generalized Group Steiner Tree Problem

Statement dc:rights

• Copyright 2025 Darkhan Baizhan

Language dc:language

en, eng

Handle dc:identifier

https://hdl.handle.net/2142/129592

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F129592