The Euclidean Steiner Tree Problem in dimension greater than two is notoriously difficult. The successful methods for exact solution are not based on mathematical-optimization methods --- rather, they involve very sophisticated enumeration. There are two types of mathematical-optimization formulations in the literature, and it is an understatement to say that neither scales well enough to be useful. We focus on one of the formulations, a nonconvex MINLP formulation of Maculan, Michelon and Xavier. Our goal is to make some first steps in improving the formulation so that large instances may eventually be amenable to solution by a spatial branch-and-bound algorithm.
Article
View On a nonconvex MINLP formulation of the Euclidean Steiner tree problems in n-space