D'Ambrosio C.,Ecole Polytechnique - Palaiseau |
Fampa M.,Federal University of Rio de Janeiro |
Lee J.,University of Michigan |
Vigerske S.,ZIB Konrad Zuse Zentrum fur Informationstechnik Berlin
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | Year: 2015
The Euclidean Steiner Tree Problem in dimension greater than 2 is notoriously difficult. Successful methods for exact solution are not based on mathematical-optimization - rather, they involve very sophisticated enumeration. There are two types of mathematicaloptimization formulations in the literature, and it is an understatement to say that neither scales well enough to be useful. We focus on a known nonconvex MINLP formulation. 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. Along the way, we developed a new feature which we incorporated into the global-optimization solver SCIP and made accessible via the modeling language AMPL, for handling piecewise-smooth univariate functions that are globally concave. © Springer International Publishing Switzerland 2015.