Abstract | ||
---|---|---|
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 mathematical-optimization 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. |
Year | DOI | Venue |
---|---|---|
2015 | 10.1007/978-3-319-20086-6_10 | SEA |
Field | DocType | Volume |
Mathematical optimization,Understatement,Steiner tree problem,Computer science,Enumeration,Modeling language,Euclidean geometry,Solver,Univariate,AMPL | Conference | 9125 |
ISSN | Citations | PageRank |
0302-9743 | 3 | 0.55 |
References | Authors | |
7 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Claudia D'Ambrosio | 1 | 3 | 0.55 |
Marcia Fampa | 2 | 58 | 11.69 |
JON LEE | 3 | 79 | 14.45 |
Stefan Vigerske | 4 | 119 | 10.85 |