Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

Comparing Branching Rules for the Quota Steiner Tree Problem with Interference

accepted for publication
  • Branching decisions play a crucial role in branch-and-bound algorithms for solving combinatorial optimization problems. In this paper, we investigate several branching rules applied to the Quota Steiner Tree Problem with Interference (QSTPI). The Quota Steiner Tree Problem (QSTP) generalizes the classical Steiner Tree Problem (STP) in graphs by seeking a minimum-cost tree that connects a subset of profit-associated vertices whose cumulative profit meets or exceeds a given quota. The QSTPI introduces interference among vertices: Selecting certain vertices simultaneously reduces their individual contributions to the overall profit. This problem arises, for example, in positioning and connecting wind turbines, where turbines possibly shadow other turbines, reducing their energy yield. Unlike classical STP variants, large QSTPI instances require significantly more branching to compute provably optimal solutions. In contrast to branching on variables, we utilize the combinatorial structure of the QSTPI by branching on the graph's vertices. We adapt classical and problem-specific branching rules and present a comprehensive computational study comparing the effectiveness of these branching strategies.
Metadaten
Author:Jaap PedersenORCiD, Niels LindnerORCiD, Daniel RehfeldtORCiD, Thorsten KochORCiD
Document Type:In Proceedings
Parent Title (English):Operations Research Proceedings 2025
Year of first publication:2026
Preprint:urn:nbn:de:0297-zib-101250
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.