NETWORK OPTIMIZATION MODELS:THE MINIMUM SPANNING TREE PROBLEM

THE MINIMUM SPANNING TREE PROBLEM

The minimum spanning tree problem bears some similarities to the main version of the shortest-path problem presented in the preceding section. In both cases, an undirected and connected network is being considered, where the given information includes some mea- sure of the positive length (distance, cost, time, etc.) associated with each link. Both problems also involve choosing a set of links that have the shortest total length among all sets of links that satisfy a certain property. For the shortest-path problem, this property is that the chosen links must provide a path between the origin and the destination. For the minimum spanning tree problem, the required property is that the chosen links must provide a path between each pair of nodes.

The minimum spanning tree problem can be summarized as follows:

1. You are given the nodes of a network but not the links. Instead, you are given the po- tential links and the positive length for each if it is inserted into the network. (Alter- native measures for the length of a link include distance, cost, and time.)

2. You wish to design the network by inserting enough links to satisfy the requirement that there be a path between every pair of nodes.

3. The objective is to satisfy this requirement in a way that minimizes the total length of the links inserted into the network.

A network with n nodes requires only (n - 1) links to provide a path between each pair of nodes. No extra links should be used, since this would needlessly increase the to-

tal length of the chosen links. The (n - 1) links need to be chosen in such a way that the resulting network (with just the chosen links) forms a spanning tree (as defined in Sec. 10.2). Therefore, the problem is to find the spanning tree with a minimum total length of the links.

Figure 10.5 illustrates this concept of a spanning tree for the Seervada Park problem (see Sec. 10.1). Thus, Fig. 10.5a is not a spanning tree because nodes O, A, B, and C are not connected with nodes D, E, and T. It needs another link to make this connection. This network actually consists of two trees, one for each of these two sets of nodes. The links in Fig. 10.5b do span the network (i.e., the network is connected as defined in Sec. 10.2), but it is not a tree because there are two cycles (O–A–B–C–O and D–T–E–D). It has too many links. Because the Seervada Park problem has n = 7 nodes, Sec. 10.2 indicates that the network must have exactly n - 1 = 6 links, with no cycles, to qualify as a spanning tree. This condition is achieved in Fig. 10.5c, so this network is a feasible solution (with a value of 24 miles for the total length of the links) for the minimum spanning tree prob- lem. (You soon will see that this solution is not optimal because it is possible to construct a spanning tree with only 14 miles of links.)

Some Applications

Here is a list of some key types of applications of the minimum spanning tree problem:

1. Design of telecommunication networks (fiber-optic networks, computer networks, leased-line telephone networks, cable television networks, etc.)

2. Design of a lightly used transportation network to minimize the total cost of provid- ing the links (rail lines, roads, etc.)

3. Design of a network of high-voltage electrical power transmission lines

4. Design of a network of wiring on electrical equipment (e.g., a digital computer sys- tem) to minimize the total length of the wire

5. Design of a network of pipelines to connect a number of locations

In this age of the information superhighway, applications of this first type have become particularly important. In a telecommunication network, it is only necessary to insert enough links to provide a path between every pair of nodes, so designing such a network is a classic application of the minimum spanning tree problem. Because some telecommunication networks now cost many millions of dollars, it is very important to optimize their design by finding the minimum spanning tree for each one.

An Algorithm

The minimum spanning tree problem can be solved in a very straightforward way because it happens to be one of the few OR problems where being greedy at each stage of the solution procedure still leads to an overall optimal solution at the end! Thus, beginning with any node, the first stage involves choosing the shortest possible link to another node, without worrying about the effect of this choice on subsequent decisions. The second stage involves identify- ing the unconnected node that is closest to either of these connected nodes and then adding the corresponding link to the network. This process is repeated, per the following summary, until all the nodes have been connected. (Note that this is the same process already illustrated in Fig. 10.3 for constructing a spanning tree, but now with a specific rule for selecting each new link.) The resulting network is guaranteed to be a minimum spanning tree.

Algorithm for the Minimum Spanning Tree Problem

1. Select any node arbitrarily, and then connect it (i.e., add a link) to the nearest distinct node.

2. Identify the unconnected node that is closest to a connected node, and then connect these two nodes (i.e., add a link between them). Repeat this step until all nodes have been connected.

3. Tie breaking: Ties for the nearest distinct node (step 1) or the closest unconnected node (step 2) may be broken arbitrarily, and the algorithm must still yield an optimal solu- tion. However, such ties are a signal that there may be (but need not be) multiple op- timal solutions. All such optimal solutions can be identified by pursuing all ways of breaking ties to their conclusion.

The fastest way of executing this algorithm manually is the graphical approach il- lustrated next.

Applying This Algorithm to the Seervada Park Minimum Spanning Tree Problem

The Seervada Park management (see Sec. 10.1) needs to determine under which roads telephone lines should be installed to connect all stations with a minimum total length of line. Using the data given in Fig. 10.1, we outline the step-by-step solution of this problem.

Nodes and distances for the problem are summarized below, where the thin lines now represent potential links.

Although it may appear at first glance that the choice of the initial node will affect the resulting final solution (and its total link length) with this procedure, it really does not. We suggest you verify this fact for the example by reapplying the algorithm, starting with nodes other than node O.

The minimum spanning tree problem is the one problem we consider in this chapter that falls into the broad category of network design. In this category, the objective is to design the most appropriate network for the given application (frequently involving transportation systems) rather than analyzing an already designed network.