{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/129592"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/129592","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Generalized Group Steiner Trees","abstract":"Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2027-05-01","abstract_html":"Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2027-05-01","abstract_has_math":false,"creators":["Baizhan, Darkhan"],"institution":"University of Illinois Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Industrial Engineering","degree_department":null,"school":null,"contributors":["Vogiatzis, Chrysafis"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2025,"date_issued":"2025-04-28","date_published":"2025-04-28","updated_at":"2026-07-22T22:25:05Z","subjects":["Combinatorial Optimization","Integer Programming","Group Steiner Tree Problem","Generalized Group Steiner Tree Problem"],"languages":["en","eng"],"rights":["Copyright 2025 Darkhan Baizhan"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/129592","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Vogiatzis, Chrysafis"]},{"key":"dc:creator","label":"Author","values":["Baizhan, Darkhan"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2025-04-28","2025-05"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Industrial Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Combinatorial Optimization","Integer Programming","Group Steiner Tree Problem","Generalized Group Steiner Tree Problem"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en","eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2025 Darkhan Baizhan"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/129592"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2027-05-01","The student, Darkhan Baizhan, accepted the attached license on 2025-04-28 at 11:29.","The student, Darkhan Baizhan, submitted this Thesis for approval on 2025-04-28 at 11:29.","This Thesis was approved for publication on 2025-04-28 at 12:37.","DSpace SAF Submission Ingestion Package generated from Vireo submission #22032 on 2025-10-19 at 19:16:23","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."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Generalized Group Steiner Trees"]}]}],"canonical_facts":{"dc:contributor":["Vogiatzis, Chrysafis"],"dc:creator":["Baizhan, Darkhan"],"dc:date":["2025-04-28","2025-05"],"dc:description":["Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2027-05-01","The student, Darkhan Baizhan, accepted the attached license on 2025-04-28 at 11:29.","The student, Darkhan Baizhan, submitted this Thesis for approval on 2025-04-28 at 11:29.","This Thesis was approved for publication on 2025-04-28 at 12:37.","DSpace SAF Submission Ingestion Package generated from Vireo submission #22032 on 2025-10-19 at 19:16:23","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."],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/129592"],"dc:language":["en","eng"],"dc:rights":["Copyright 2025 Darkhan Baizhan"],"dc:subject":["Combinatorial Optimization","Integer Programming","Group Steiner Tree Problem","Generalized Group Steiner Tree Problem"],"dc:title":["Generalized Group Steiner Trees"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Industrial Engineering"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:05Z"}