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

2004, Volume 3, Issue 2

Section

Articles

License

International Journal of Computing is an open access journal. Authors who publish with this journal agree to the following terms:
•    Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
•    Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
•    Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.