A Specialized Branch and Bound Method for the Euclidean Steiner Problem in Rn

In this text, we present an application of the Branch and Bound method with geometric pruning constraints to the Euclidean Steiner Problem in $\Re^n$. We propose a new greedy strategy for determining strong upper bounds, using a breadth-first search algorithm and a minimum spanning tree. A well-known second-order conic programming model, along with the Mosek solver, are employed in solving each subproblem during the algorithm's execution, determining the optimal location of the Steiner points. Additionally, we present a sorting scheme for the problem's input points and investigate the effect of this strategy, as well as geometric pruning and upper bounds, on the number of subproblems solved during the application of the exact algorithm for each input instance.