Solving Large Steiner Tree Problems in Graphs for Cost-Efficient
  Fiber-To-The-Home Network Expansion
  The expansion of Fiber-To-The-Home (FTTH) networks creates high costs due to
expensive excavation procedures. Optimizing the planning process and minimizing
the cost of the earth excavation work therefore lead to large savings.
Mathematically, the FTTH network problem can be described as a minimum Steiner
Tree problem. Even though the Steiner Tree problem has already been
investigated intensively in the last decades, it might be further optimized
with the help of new computing paradigms and emerging approaches. This work
studies upcoming technologies, such as Quantum Annealing, Simulated Annealing
and nature-inspired methods like Evolutionary Algorithms or slime-mold-based
optimization. Additionally, we investigate partitioning and simplifying
methods. Evaluated on several real-life problem instances, we could outperform
a traditional, widely-used baseline (NetworkX Approximate Solver) on most of
the domains. Prior partitioning of the initial graph and the presented
slime-mold-based approach were especially valuable for a cost-efficient
approximation. Quantum Annealing seems promising, but was limited by the number
of available qubits.
