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.
| 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 |

