Optimization Online


On a nonconvex MINLP formulation of the Euclidean Steiner tree problems in n-space

Claudia D'Ambrosio (dambrosio***at***lix.polytechnique.fr)
Marcia Fampa (fampa***at***cos.ufrj.br)
Jon Lee (jonxlee***at***umich.edu)
Stefan Vigerske (vigerske***at***zib.de)

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

Keywords: Euclidean Steiner Tree, spatial branch-and-bound, MINLP

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 2: Combinatorial Optimization

Category 3: Global Optimization


Download: [PDF]

Entry Submitted: 09/05/2014
Entry Accepted: 09/05/2014
Entry Last Modified: 02/12/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society