SOLVING THE RECTILINEAR STEINER MINIMAL TREE PROBLEM WITH A BRANCH AND CUT ALGORITHM

Authors

  • Nahit Emanet
  • Can Ozturan

DOI:

https://doi.org/10.47839/ijc.3.2.290

Keywords:

Combinatorial problems, Minimum spanning hypertree, Submodular functions, Branch-and-cut algorithm, Separation of cutting planes, Maximum flow network

Abstract

This paper presents a new branch-and-cut algorithm that allows us to reduce the solution time of the concatenation phase of the rectilinear Steiner minimal tree problem in the plane. Our branch-and-cut algorithm is used on an integer programming formulation using what we call cutsec, and sec constraints. We present implementation details of our branch-and-cut program called NEOSteiner and provide computational results on test instances from the SteinLib library.

References

M.R. Garey. D.S. Johnson. The rectilinear Steiner problem is NP-Complete, SIAM J. Appl. Math. 32 (1977). p. 826-834.

F.K. Hwang. D.S. Richards. P. Winter. The Steiner tree problem. Elsevier Science Publishers. Amsterdam, The Netherlands, 1990.

D.M. Warme. P. Winter. M. Zachariasen. Exact algorithms for plane Steiner tree problems: A computational study. in: D-Z. Du. J.M. Smith. J.H. Rubinstein. (Editors), Advances in Steiner Trees. Kluwer Academic Publishers. Massachusetts, 2000. p. 81-116.

T. Polzin. S.V. Daneshmand. On Steiner trees and minimum spanning trees in hypergraphs, Operations Research Letters 31 (2003). p. 12-20.

G. Robins. On optimal interconnections, PhD thesis, Department of Computer Science, UCLA, 1992.

I. Mandiou. V. Vazirani. J. Ganley. A new heuristic for rectilinear Steiner trees. IEEE Transactions on CAD, 19 (2000). 1129-1139.

D.M. Warme. Spanning trees in hypergraphs with applications to Steiner trees, PhD thesis, Department of Computer Science, The University of Virginia, 1998.

G.L. Nemhauser. L.A. Wolsey. Integer and Combinatorial Optimization. Wiley-Interscience Publication, 1988.

L.R. Ford. D.R. Fulkerson. Flows in Network. Princeton University Press, New Jersey, 1962.

C. Bron. J. Kerbosch. Finding of all cliques of an undirected graph, Comm. ACM. 16 (1973) p. 575-577.

M. Padberg. L. Wolsey. Trees and cuts, Annals of Discrete Mathematics, 17 (1983).

D. Applegate. R. Bixby. V. Chvatal. W. Cook. Finding cuts in the TSP, Technical Report, Mathematics, AT&T Bell Laboratories, NJ, 1994.

N. Emanet. NEOSteiner program. http://asma.cmpe.boun.edu.tr/~emanetn/NEO.html.

T. Koch. A. Martin. SteinLib. http://elib.zib.de/steinlib/steinlib.php.

N. Emanet. C. Ozturan. Dogrulu Steiner agac problemlerinin seri ve paralel algoritmalar ile cozumu, in: F.E. Sevilgen. H. Sadikouglu. (Editors), Yuksek Performansli Bilisim Sempozyumu, Gebze YTE, Kocaeli, 2002. p. 35-38.

Downloads

Published

2014-08-01

How to Cite

Emanet, N., & Ozturan, C. (2014). SOLVING THE RECTILINEAR STEINER MINIMAL TREE PROBLEM WITH A BRANCH AND CUT ALGORITHM. International Journal of Computing, 3(2), 81-87. https://doi.org/10.47839/ijc.3.2.290

Issue

Section

Articles