Operations Research 2025
Abstract Submission

2236. Comparing Branching Rules for the Quota Steiner Tree Problem with Interference

Invited abstract in session WB-4: Network Optimization, stream Discrete and Combinatorial Optimization.

Wednesday, 10:45-12:15
Room: H6

Authors (first author is the speaker)

1. Jaap Pedersen
Applied Algorithmic Intelligence Methods, Zuse Institute Berlin
2. Niels Lindner
Optimization, Zuse Institute Berlin
3. Daniel Rehfeldt
Mathematical Algorithmic Intelligence, Zuse Institut Berlin
4. Thorsten Koch
Applied Algorithmic Intelligence Methods, ZIB / TU Berlin

Abstract

Branching decisions play a crucial role in branch-and-bound algorithms for solving combinatorial optimization problems. In this talk, we investigate several branching rules applied to the Quota Steiner Tree Problem with Interference (QSTPI). The original 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 together 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 prove optimality. 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.

Keywords

Status: accepted

Back to the list of papers