Solving a Steiner Tree Problem in Excel

  Solving a Steiner tree problem can be challenging but I managed to get Excel to do this using an iterative process for correcting the positions of the unknown points. The problem seeks to find a set of links between a number of points that has a minimal sum for the lengths. One can derive the minimum conditions as follows. The required condition is that the sum of a set of unit vectors toward or away from the unknown points x and y is equal to zero.

Note that the conditions imply that these unit vectors can be arranged to form the sides of an equilateral triangle making the angles at the points x and y equal to 120°.

The conditions for minimum are not linear making them difficult to solve for x and y but we can linearize them by assuming values for x and y and seeking corrections dx and dy for which the above functions are zero.

The values for x and y allow one to find the corrections dx and dy which produce the more accurate solutions x' and y'. One nice thing about Excel is that one can use a macro to replace the original values of x and y with the new ones, x' and y', and rapidly recompute them using a shortcut key such as Ctrl-Shift-R.