TY  - CONF
A1  - Pedersen, Jaap
A1  - Lindner, Niels
A1  - Rehfeldt, Daniel
A1  - Koch, Thorsten
T1  - Comparing Branching Rules for the Quota Steiner Tree Problem with Interference
T2  - Operations Research Proceedings 2025
N2  - 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.
Y1  - 2026
UR  - https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/10297
ER  -