Comparing Branching Rules for the Quota Steiner Tree Problem with Interference
Please always quote using this URN: urn:nbn:de:0297-zib-101250
- 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 to meet a given quota. The extended version, 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. While exact solvers for standard STP-related problems often rely heavily on reduction techniques and cutting-plane methods – rarely generating large branch-and-bound trees – experiments reveal that large instances of QSTPI 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: | ZIB-Report |
| MSC-Classification: | 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING |
| CCS-Classification: | J. Computer Applications |
| Date of first Publication: | 2025/08/25 |
| Series (Serial Number): | ZIB-Report (25-16) |
| ISSN: | 1438-0064 |

