Optimization Online


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

Marcia Fampa(fampa***at***cos.ufrj.br)
Jon Lee(jonxlee***at***umich.edu)
Wendel Melo(wendelmelo***at***cos.ufrj.br)

Abstract: We present a specialized branch-and-bound (b&b) algorithm for the Euclidean Steiner tree problem (ESTP) in 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

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

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )


Download: [PDF]

Entry Submitted: 11/16/2014
Entry Accepted: 11/17/2014
Entry Last Modified: 11/16/2014

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