SOLVING THE RECTILINEAR STEINER MINIMAL TREE PROBLEM WITH A BRANCH AND CUT ALGORITHM - Emanet, Nahit; Ozturan, Can (International Journal of Computing, 2014)
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.