Department of Computer Science
  ^†University of Kentucky         *Texas Tech University
Lexington, Kentucky 40506         Lubbock, Texas

Of special interest in this paper are local improvement algorithms. This kind of approach involves exploring chains of closely related feasible solutions to a problem in hope of discovering a better answer. Two of recent vintage [CH90, HaVW90] involve redesigning small subtrees and adding Steiner points to small subtrees.

Our approach differs significantly from these. Using a new representation for Steiner trees which allows us to separate them into subtrees and reconnect the subtrees with comparative ease, we are able to easily define traversals between neighboring configurations. This results in an algorithm which is easily describable and easily implementable, as well as providing substantial improvement over existing heuristic algorithms for the rectilinear Steiner problem.

A rectilinear Steiner spanning tree over a set of points is a connected collection of vertical and horizontal lines which spans the points. We shall refer to these sets of lines as Steiner trees. Presenting the very special member of this collection of spanning trees known as the shortest tree is the goal of our construction efforts.

We are able to restrict our feasible solution search space to a finite collection of trees by applying Hanan's classic result which states that a shortest Steiner tree exists on the grid induced by the points [Han66]. This induced grid is formed by drawing vertical and horizontal lines through the points. An example of a grid induced by four points is found in figure 1a.

The shortest Steiner tree over these points appears in figure 1c. Another type of spanning tree, the rectilinear minimum spanning tree over the same set of points occupies figure 1b. These differ from Steiner trees in that they are sets of edges between points while Steiner trees are collections of grid edges spanning the points. This means that any overlaps between edges in minimum spanning trees are counted twice when computing the size of the tree whereas Steiner trees contain no overlaps. The relationship between the sizes of these two kinds of spanning trees has been formulated by Hwang [Hw76].

Minimal spanning trees are easily defined as sets of edges. For example, the tree in figure 1b is exactly the three edges: <a, c>, <a, b>, and <c, d>. The Steiner tree of figure 1c contains these three edges too, but they are drawn differently, and if the overlaps between edges are not included twice when determining the length of the tree, the shortest possible Steiner spanning tree over the points is formed.

In order to be able to define Steiner trees as sets of edges between points (rather than collections of grid edges or lines on the grid), we use a result from [JLV96] which guarantees that there is a shortest Steiner tree with the following two properties.

More ease of definition and construction is provided if we require the points to induce an n by n grid and only consider trees with no dangling lines (lines which do not end at another line or a point). We claim that this is not overly restrictive since dangling lines are never found in shortest spanning trees and there is little difference in spanning trees for a set of points containing two which share a coordinate and a set where the points nearly share a coordinate.

Thus given a set of n points which do not share horizontal or vertical coordinates, a Steiner spanning tree of the kind we have defined consists of exactly n lines, one for each point. We call these 1-1 rectilinear Steiner spanning trees (or 1-1 Steiner trees) because the lines and points form a one to one correspondence. As the following theorem states, they may be defined as sets of edges.

As we have seen, figure 1c contains such a tree. The result concerning shortest Steiner trees and 1-1 trees mentioned above is stated as follows.

These results also provide limits which we may use to restrict our feasible solution search space. Thus we may now confine our investigations only to 1-1 Steiner trees represented as sets of edges or point pairs and be confident that a shortest Steiner spanning tree is contained within this abridged solution space. Keeping in mind that an edge is a pair of points, we now redefine Steiner spanning trees.

Since the Steiner trees which interest us are now merely sets of edges, we shall employ the notation T = {<u₁,v₁>, ... , < u_n-1,v_n-1>} when referring to the n-1 edges which make up one of these trees.

As we found when examining figure 1, there is no unique way to draw a tree represented by a set of edges. If we are drawing 1-1 Steiner trees though, there are exactly two ways since each line in the tree can be vertical or horizontal. To draw a tree from a set of edges we begin with an edge (or pair of points) and connect them with a vertical line through one and a horizontal line through the other. Then we take another edge containing one of these points and connect in the new point (from this new edge) with a line perpendicular to an existing line and possibly an extension of that existing line. We continue on in the same manner until all of the edges have been used and the entire tree is drawn. The process produces a spanning tree over the points since the set of edges spans the points.

For example, the tree in figure 1c can be constructed by drawing the edge <a, c> with a horizontal line through a, connecting this to the point b with the edge <a, b>, and then filling in the edge <c, d>. This construction sequence is presented in figure 2.

Note that figure 1b is the other way to draw the 1-1 Steiner tree represented by the same set of edges. It was constructed by connecting edges in the same sequence, but beginning with a vertical line through a and a horizontal one through c.

Since we now have two physically different tree drawings for each set of edges, we often have two different sizes also. Thus we must define what is meant by the size of a tree for a set of edges. The following definition sets this to our best advantage.

Local improvement algorithms involve sequences of small changes to some initial feasible solution which lead (one hopes) to an optimum solution. Each small change should not produce a new tree which is very different from the previous one. Small changes such as these are said to lead to neighbors of the original tree. If we are to use this technique to develop a shortest Steiner tree construction algorithm, we must formulate exactly what the neighborhood for a solution consists of, which in this case is the neighborhood of a 1-1 Steiner tree.

Intuitively, this process shall be very simple. We break a tree into two subtrees by removing an edge and then patch it back together with a different edge to produce a neighbor. The collection of trees constructed in this manner forms the neighborhood of our original tree.

We define this tree separation formally as follows.

Our next step is to patch the tree back together to produce a neighboring spanning tree over the set of points. This means adding an edge which joins the two subtrees. The edges possible to add to the subtrees of our example are <a, d>, <b, c>, and <b, d>. Adding these edges and drawing each new tree in both possible ways is demonstrated in figure 4.

In reconnecting the subtrees we did not use the edge <a, c> because we had no further interest in that spanning tree. We had already considered it and we wished to construct new and different spanning trees. Note that the definitions provided below do include a tree in its own neighborhood - but we shall ignore this when developing tree construction algorithms.

Definitions of this transformation process and its transitive closure are as follows.

We now have the tools with which to implement a local improvement strategy based upon traversing sequences of best neighbors. But, it is not clear that it is possible to get to the optimum solution, the smallest 1-1 Steiner tree from just any starting place. We would like to be sure that the restrictions so carefully formulated above place no additional barriers in our way when attempting to find the optimum spanning tree. The following lemma provides a way to select specific neighbors which might be found on the path to an optimum tree.

With this lemma we now have the mechanism necessary to transform one tree into any other by selecting a sequence of transformations leading from that 1-1 tree to the one we wish to construct.

This means that by restricting our field of inquiry to 1-1 Steiner trees it is possible to construct an optimum solution to the rectilinear Steiner spanning problem by traversing a sequence of transformations between neighboring 1-1 trees, starting from any tree. Thus theorem 4 assures us that a local search algorithm based upon the neighborhoods defined above always has a chance of finding the best solution.

This method involves starting with some feasible solution and examining all of its neighbors. The best of these is selected and then its neighbors are examined. This process usually continues for O(n) steps (with problems of size n) producing a sequence feasible solutions found in a chain of neighborhoods. The best solution in the sequence is selected and the entire algorithm is repeated until no improvement is achieved. A template for this local search procedure follows.

One reason that these algorithms work so well is that a local optimum within a certain radius of neighborhoods is found in each of the repeat loops. If the sequence of neighbors traversed is large enough then there is a chance of encountering a global optimum.

We begin by taking as our initial 1-1 Steiner spanning tree the set of edges in the minimal rectilinear spanning tree. Then we construct the smallest neighboring 1-1 tree by applying a transformation of the kind discussed in the last section. (Breaking the tree apart by removing an edge and then adding another edge to reconnect it.) Then we examine this tree in turn and find its smallest neighbor. And so on.

To insure that this process halts, we do not allow returning to previous configurations. This is accomplished by locking in place the replacement edges used to form neighboring trees. Thus we do not undo what we have accomplished and we prevent cycling.

When we have replaced n-1 edges (for an n point problem) we examine the sequence of 1-1 trees we have built and select the smallest. Then we begin again (with this as our starting point) and keep iterating until no improvement is found. This process is described in the algorithm of figure 6.

At the core of the local improvement algorithm is the transformation of a tree into its most attractive neighbor. We accomplish this by examining all of the possible ways to break a tree into subtrees by removing one edge as well as every manner in which we can reconnect it. To prevent cycling in the main algorithm though, we do not consider neighbors formed by removing edges which were added earlier. (These are referred to as locked edges.) Figure 7 contains this neighbor selection procedure.

Two properties of the algorithm need to be demonstrated, termination and correctness. Termination is assured since the main algorithm does halt when it encounters no better 1-1 Steiner tree at the end of the repeat loop. Since we began with a particular tree (the minimal spanning tree) and required a smaller tree to be found before iterating once more, this is a finite process.

An efficiency limit for our local search algorithm comes directly from Hwang's theorem [Hw76] and the observation that a tree larger than the minimal spanning tree cannot be selected.

Complexity depends upon the time spent in examining neighbors. Examination of the neighbor selection algorithm of figure 7 reveals that inside the loops we need to find the size of a tree formed by removing an edge and adding one to the original tree. The proper data structure allows us to keep this time to a minimum. We use a list of the intersections on each line. Consider table 1 below and the spanning trees of figure 1.

The column of lines on the left represents the spanning tree in figure 1b. Through the point a we have a vertical line which goes from c's row to b's row. In the column of lines on the right (depicting the spanning tree in figure 1c) we note that the line through point a is horizontal, begins at point a, ends at point c, and contains an intersection at b's column.

Deleting an edge from a tree involves changing the lines through the two points defining the edge so that the edge's intersection no longer appears. If the intersection is at the end of the line then the new line is shorter than before. For example, deleting <a, c> from the tree of figure 1b changes the line through a to a-b and the line through c to c-d. Adding the edge <b, d> to this changes the line through b to a-b-d and that through d to c-d-b. Thus to add or delete an edge we need to insert or delete an intersection on the list of rows or columns which make up the lines through the points which define the edge. If the line lists are stored as search trees then O(log n) steps are required

Computing the length of a new tree is even less complex if pointers to the ends of each line (the leftmost and rightmost leaves in the search tree) are maintained. Since trees change size when intersections are added to or removed from the ends of lines, calculating changes in size requires only a constant amount of time.

The two inner for loops of the BestNeighbor procedure contribute O(n²) steps for each unlocked pair processed since only O(1) steps are executed inside the loops. So, the first time the neighbor selection routine is called, O(n³) steps are executed, and the last time, O(n²) steps are completed since there is only one unlocked pair. This adds up to O(n⁴) steps each time the outer loop is executed (which in practice is usually about twice).

The algorithm was implemented in C and executed on a Sequent Symmetry S81 Dynix 3.0 machine with randomly generated input data sets. There were ten data sets for each number of points (which ranged from 5 to 100). All of the data sets were generated randomly from a uniform distribution in a grid, which has been found to be very similar to pin locations of actual VLSI layouts [KR90] and thus appears to be an appropriate testbed for these problems [Ric89].

Since O(n⁴) steps, while polynomial, is a rather large complexity for an algorithm, the actual execution times for the algorithm are of interest. In table 2, the average time (in seconds) is provided for each group of data sets. As expected, very large data sets do require long times, but for problems of the size expected in most applications, the times are not excessive. And, since the neighborhood search lends itself nicely to parallel computation methods, even large problems would take only minor amounts of time if implemented in this manner.

Table 3 provides a comparison of the local improvement algorithm to other algorithms for the groups of various sized point sets. Included are a Kruskal style MST-based algorithm from [LV91], two classic Prim style MST-based algorithms from [LBH76, Hw76], and two linear algorithms [HoVW90, LPV91].

For the data sets containing five points, the local improvement solutions were the same size as those found by an optimal branch and bound method [LPV92]. It was the only heuristic to accomplish this. And, on ten point data, the local improvement algorithm found an optimum solution in five of the ten cases. In addition, it came close to the optimum branch and bound algorithm's score of 10.84% average improvement over the minimal spanning trees for this group.

We have presented an easily described, new approach to solving the rectilinear Steiner problem. The algorithm is very practical for problem sizes corresponding to actual VLSI layouts and provides significant improvement over algorithms employing other popular methods.

CH90 Chao, T.-H., and Hsu, Y.-C. "Rectilinear Steiner Tree Construction by Local and Global Refinement." Proc. of IEEE Int. Conf. on CAD, 1990, 432 - 435.

Han66 Hanan, M. "On Steiner's Problem with Rectilinear Distance." SIAM J. Appl. Math., vol. 14, no. 2, 1966, 255-265.

HaVW90 Hasan, N., Vijayan, G., and Wong, C. K. "A Neighborhood Improvement Algorithm for Rectilinear Steiner Trees," Proc. ISCAS, 1990, 2869 - 2872.

HoVW90 Ho, J.-M., Vijayan, G., and Wong, C. K. "New Algorithms for the Rectilinear Steiner Tree Problem." IEEE Trans. on CAD, vol.9, 1990, 185-193.

Hw76 Hwang, F. K. "On Steiner Minimal Trees with Rectilinear Distance." SIAM J. Appl. Math., vol. 30, 1976, 104-114.

HRW92 Hwang, F. K., Richards, D. S., and Winter, P. The Steiner Tree Problem, Annals of Discrete Mathematics, no. 53, North Holland, 1992.

JLV96 Joyce, P. M., Lewis, F. D., and VanCleave, N. "The Feasible Solution Space for Steiner Trees." Proceedings of the Eighth Society for Industrial and Applied Mathematics Conference on Discrete Mathematics, 1996.

KR90 Kahng, A. and Robins, G. "On a New Class of Iterative Steiner Tree Heuristics with Good Performance." Proc. of IEEE Int. Conf. on CAD, 1990, 428 - 431.

KL70 Kernighan, B. W. and Lin, S. "An Efficient Heuristic Procedure for Partitioning Graphs." Bell System Technical J., vol. 49, 1970, 291-307.

LBH76 Lee, J. H., Bose, N. K., and Hwang, F. K. "Use of Steiner's Problem in Suboptimal Routing in Rectilinear Metric." IEEE Trans. on Circuits Syst., vol. CAS-23, 1976, 470-476.

LPV91 Lewis, F. D., Pong, W. C., and Van Cleave, N. "A Linear-time Heuristic for Rectilinear Steiner Trees." Proc. of First Great Lakes Sym. on VLSI, 1991, 152-156.

LPV92 Lewis, F. D., Pong, W. C., and Van Cleave, N. "Optimum Steiner Tree Generation." Proc. of Second Great Lakes Sym. on VLSI, 1992, 207 - 212.

LV91 Lewis, F. D. and Van Cleave, N. "Correct and Provably Efficient Methods for Rectilinear Steiner Spanning Tree Generation," Proceedings of the First Great Lakes Computer Science Conference, and Springer-Verlag Lecture Notes, vol. 507, 1991.

Ric89 Richards, D. "Fast Heuristic Algorithms for Rectilinear Steiner Trees." Algorithmica, vol. 4, 1989, 191-207.

Van92 Van Cleave, N. "The Rectilinear Steiner Problem." PhD Dissertation, CS Department, University of Kentucky, Lexington, KY, 1992.