A specialized branch-and-bound algorithm for the Euclidean Steiner tree problem in n-space

Marcia Fampa (), Jon Lee () and Wendel Melo ()
Additional contact information
Marcia Fampa: Universidade Federal do Rio de Janeiro
Jon Lee: University of Michigan
Wendel Melo: PESC/COPPE, Universidade Federal do Rio de Janeiro

Computational Optimization and Applications, 2016, vol. 65, issue 1, No 2, 47-71

Abstract: Abstract We present a specialized branch-and-bound (b&b) algorithm for the Euclidean Steiner tree problem (ESTP) in $$\mathbb {R}^n$$ R n and apply it to a convex mixed-integer nonlinear programming (MINLP) formulation of the problem, presented by Fampa and Maculan. The algorithm contains procedures to avoid difficulties observed when applying a b&b algorithm for general MINLP problems to solve the ESTP. Our main emphasis is on isomorphism pruning, in order to prevent solving several equivalent subproblems corresponding to isomorphic Steiner trees. We introduce the concept of representative Steiner trees, which allows the pruning of these subproblems, as well as the implementation of procedures to fix variables and add valid inequalities. We also propose more general procedures to improve the efficiency of the b&b algorithm, which may be extended to the solution of other MINLP problems. Computational results demonstrate substantial gains compared to the standard b&b for convex MINLP.

Keywords: Euclidean Steiner tree problem; Mixed-integer nonlinear programming; Branch-and-bound; Isomorphism pruning (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s10589-016-9835-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:coopap:v:65:y:2016:i:1:d:10.1007_s10589-016-9835-z

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-016-9835-z

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().