CONFIGURING A PRIVATE LINE CIRCUIT ACCORDING TO THE HI-LO TARIFF - A MINIMAL STEINER TREE PROBLEM.

Presented is a heuristic algorithm for configuring a multipoint private line circuit according to the new Hi-Lo Tariff. This problem, which can be posed as the classical one of finding the minimal Steiner tree in a graph, is unsolved in the sense that obtaining the global optimum by known procedures requires an amount of computation which increases exponentially in the input parameters. The heuristic is an algorithm whose computation time increases only as a polynomial in the input parameters (and hence is computationally efficient). In 35 test problems, which were small enough to be solved exactly by enumeration, the algorithm found the optimum in all but one case (and then its error was only 0. 4 percent in cost). In 35 larger test problems, no network designed by the procedure was more expensive than the counterpart found by another method.