On a nonconvex MINLP formulation of the euclidean steiner tree problem in n-space

Claudia D’Ambrosio; Marcia Fampa; Jon Lee; Stefan Vigerske

doi:10.1007/978-3-319-20086-6_10

On a nonconvex MINLP formulation of the euclidean steiner tree problem in n-space

Claudia D’Ambrosio
, Marcia Fampa
, Jon Lee
, Stefan Vigerske

Instituto de Biofisica da UFRJ
University of Michigan, Ann Arbor
ZIB (Konrad-Zuse-Zentrum für Informationstechnik Berlin)

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

8 Citations (Scopus)

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 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.

Original language	English
Title of host publication	Experimental Algorithms - 14th International Symposium, SEA 2015, Proceedings
Editors	Evripidis Bampis
Publisher	Springer Verlag
Pages	122-133
Number of pages	12
ISBN (Print)	9783319200859
DOIs	https://doi.org/10.1007/978-3-319-20086-6_10
Publication status	Published - 1 Jan 2015
Event	14th International Symposium on Experimental Algorithms, SEA 2015 - Paris, France Duration: 29 Jun 2015 → 1 Jul 2015

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9125
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	14th International Symposium on Experimental Algorithms, SEA 2015
Country/Territory	France
City	Paris
Period	29/06/15 → 1/07/15

Access to Document

10.1007/978-3-319-20086-6_10

Cite this

D’Ambrosio, C., Fampa, M., Lee, J., & Vigerske, S. (2015). On a nonconvex MINLP formulation of the euclidean steiner tree problem in n-space. In E. Bampis (Ed.), Experimental Algorithms - 14th International Symposium, SEA 2015, Proceedings (pp. 122-133). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9125). Springer Verlag. https://doi.org/10.1007/978-3-319-20086-6_10

D’Ambrosio, Claudia ; Fampa, Marcia ; Lee, Jon et al. / On a nonconvex MINLP formulation of the euclidean steiner tree problem in n-space. Experimental Algorithms - 14th International Symposium, SEA 2015, Proceedings. editor / Evripidis Bampis. Springer Verlag, 2015. pp. 122-133 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{a0517093f13f4ff5babff3e99ce30a9e,

title = "On a nonconvex MINLP formulation of the euclidean steiner tree problem in n-space",

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 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.",

author = "Claudia D{\textquoteright}Ambrosio and Marcia Fampa and Jon Lee and Stefan Vigerske",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2015.; 14th International Symposium on Experimental Algorithms, SEA 2015 ; Conference date: 29-06-2015 Through 01-07-2015",

year = "2015",

month = jan,

day = "1",

doi = "10.1007/978-3-319-20086-6\_10",

language = "English",

isbn = "9783319200859",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "122--133",

editor = "Evripidis Bampis",

booktitle = "Experimental Algorithms - 14th International Symposium, SEA 2015, Proceedings",

}

D’Ambrosio, C, Fampa, M, Lee, J & Vigerske, S 2015, On a nonconvex MINLP formulation of the euclidean steiner tree problem in n-space. in E Bampis (ed.), Experimental Algorithms - 14th International Symposium, SEA 2015, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9125, Springer Verlag, pp. 122-133, 14th International Symposium on Experimental Algorithms, SEA 2015, Paris, France, 29/06/15. https://doi.org/10.1007/978-3-319-20086-6_10

On a nonconvex MINLP formulation of the euclidean steiner tree problem in n-space. / D’Ambrosio, Claudia; Fampa, Marcia; Lee, Jon et al.
Experimental Algorithms - 14th International Symposium, SEA 2015, Proceedings. ed. / Evripidis Bampis. Springer Verlag, 2015. p. 122-133 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9125).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - On a nonconvex MINLP formulation of the euclidean steiner tree problem in n-space

AU - D’Ambrosio, Claudia

AU - Fampa, Marcia

AU - Lee, Jon

AU - Vigerske, Stefan

PY - 2015/1/1

Y1 - 2015/1/1

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-319-20086-6_10

DO - 10.1007/978-3-319-20086-6_10

M3 - Conference contribution

AN - SCOPUS:84949033988

SN - 9783319200859

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 122

EP - 133

BT - Experimental Algorithms - 14th International Symposium, SEA 2015, Proceedings

A2 - Bampis, Evripidis

PB - Springer Verlag

T2 - 14th International Symposium on Experimental Algorithms, SEA 2015

Y2 - 29 June 2015 through 1 July 2015

ER -

D’Ambrosio C, Fampa M, Lee J, Vigerske S. On a nonconvex MINLP formulation of the euclidean steiner tree problem in n-space. In Bampis E, editor, Experimental Algorithms - 14th International Symposium, SEA 2015, Proceedings. Springer Verlag. 2015. p. 122-133. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-20086-6_10

On a nonconvex MINLP formulation of the euclidean steiner tree problem in n-space

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this