Combinatorics - Spanning Tree
 This and the next page consider two combinatorial tree problems that are relatively easy to solve, the minimal spanning tree problem and the shortest path tree problem.The Optimize add-in also considers these problems (spanning tree and path tree), but provides more general solution procedures that evaluate a solution by actually placing the solution on the worksheet. The Combinatorics add-in requires that a data matrix specifying the arc lengths be provided. It uses this distance matrix and Excel computations to perform the greedy and improvement methods. For some instances of problems in this class these methods will result in the optimum solution. For others, the solutions may not be optimum. The methods of the Optimize add-in can then be used to search for the optimum. For the minimal or maximal spanning tree problems, each arc is assigned a length. The goal of the problem is to select a spanning tree so that the total of the lengths of the selected arcs is minimized or maximized. To create the problem we choose Spanning Tree from the Combinatorics menu. The figure on the left also shows the Optimize menu. The Optimize add-in performs some of the operations used by the Combinatorics add-in, so both must be installed.
Enter the name and number of nodes in the boxes provided and select the goal of maximizing or minimizing. The section at the bottom specify whether random data should be provided and the characteristics of the data.

The add-in creates a new worksheet and places the combinatorial form in upper left corner as shown below. The worksheet is given the name of the problem and a number of ranges are also labeled with the name as a prefix, so the problem name cannot be changed once the form is constructed.

The example has symmetric arc lengths with the length from node i to node j equal to the length from j to i. . The variables in the green field (row 9) describe the initial tree. The value of a variable tells where the tree arc starts. For example, the value of x2 equal to 1 means that arc (1, 2) is part of the tree. Node 1 always has x1 = 0. This means that the tree is rooted at node 1. The initial tree has a total arc length equal to 96. Although the Feasibility cells (H4 and H5) are included in the form, they play no role for the tree problems.

Greedy Solutions

The worksheet includes three buttons. The Search button transfers control to the Search dialog of the Optimize add-in where all the direct search procedures are available. The Greedy and Improve buttons construct additional matrices on the worksheet and perform algorithms that yield the greedy and improved solutions for the problem. Clicking the Greedy button, presents the dialog below.

Choosing Cancel abandons further processing. Choosing No initiates the algorithm without a graphical interface and places the result in the green field of row 9. We choose Yes to illustrate the instructional features of the add-in. The add-in places a new matrix on the worksheet below the data matrix called Greedy Measure.This matrix is created even if the graphical interface is not used, but it is deleted after the process. The user should leave the region immediately below the problem data empty of data or formulas.

The status of each node, solved or not, is shown at the borders of the matrix. The example above shows that node 1 is solved and the others are not. The add-in uses Prim's Algorithm. The algorithm adds the arc that passes from a solved node to an unsolved node with the smallest length. For the first step, only node 1 is solved, so only the arcs leaving node 1 are candidates to enter the tree. In the columns immediately to the right we see the minimum length and the node number that obtains the minimum. The first step must add the arc from 1 to 4 to the tree.

The figure below shows the next step. The cell (1, 4) is colored and outlined in the length matrix and the next arc (1, 7) is outlined in the measure matrix.

The process continues until the final solution is obtained. The measure matrix is deleted upon completion.

The variables describe the tree below, which is the minimal spanning tree rooted at node 1.

For symmetric lengths, Prim's algorithm finds the optimum for the minimal spanning tree problem, so there is no point on going further on this example.

The measure matrix performs most of the steps of Prim's Algorithm. It is entirely implemented using Excel functions, so all necessary computations are extremely rapid. The complete result is obtained in a much smaller time than when using the methods of the Optimize add-in, allowing larger problem instances to be solved in reasonable time.

Improved Solutions

To illustrate the improvement procedure we show a second example with non-symmetric arc lengths. The worksheet with the greedy solution is shown. With non-symmetric arc lengths Prim's algorithm does not necessarily obtain the optimum.

Clicking on the Improve button provides the opportunity to observe the algorithm. The figure below shows the first and also the last display for the process applied to the example. The add-in has placed the Improvement Measure matrix below the data. A cell of this matrix holds the difference between the length of an arc and the length of the current tree arc entering a node. For instance, we see that arc (4, 2) with length 16 is part of the tree, while arc (6, 2) with length 5 is not. The measure for arc (6, 2) is 5 - 16 = -11. The negative sign indicates that if arc (4, 2) were deleted and arc (6, 2) were added, the objective would decrease by 11. We do not take this step because the result would be a cycle (6, 2), (2, 3), (3, 6). Since cycles cannot be part of a tree we cannot make this improvement. The improvement step evaluates all negative numbers in the measure matrix and chooses the one that results in the most improvement without creating a cycle. It happens that several entries in the measure matrix are negative, but all form cycles with the current solution, so the improvement process terminates.
The improvement approach does not guarantee an optimum. We start with the arbitrary solution shown below. In the first step, the improvement process suggests arc (6, 3) will reduce the objective by 38.
The next step finds that arc (3, 5) can replace arc (1, 5) without forming a cycle and result in a savings of 25.
The process continues for several steps until the final solution is obtained. This happens to be the optimal directed spanning tree.

Many of the calculations required by the improvement algorithm are done using Excel worksheet functions in the measure matrix. This is much faster than the enumerative approach of the Optimize add-in, allowing larger problems to be solved.

For symmetric networks, the greedy algorithm obtains the optimum. For asymmetric the greedy method may fail to find the optimum, and the improvement algorithm also may fail.

The add-in also solves the maximum spanning tree problem. Again the greedy algorithm finds the optimum for symmetric networks, while for asymmetric networks, there is no guarantee of optimality.

Graphics

When distances are determined with a Euclidean measure, the add-in offers the opportunity to graphically display a solution. The arc lengths below are computed using the x and y coordinates in columns K and L. The lengths are truncated to integers. A new button, Map, is available.
The example is solved with the greedy method. Since all distances are positive and the matrix is symmetric, we know that this is the optimal spanning tree. Clicking the Map button causes a new worksheet to be produced with a map of the optimal solution. The gold colored node is the root node.
A more interesting map is the minimal spanning tree solution of the 48 city problem att48. The data for this problem represents the 48 state capitals of the continental United States. The TSP solution is on another page of this section.

Operations Research Models and Methods
Internet
by Paul A. Jensen