An efficient decomposition algorithm to optimize spare capacity in a telecommunications network

This article presents a new model for the spare capacity allocation problem in a self-healing, mesh SONET telecommunications network. This model is known as the spare capacity network flow model and has not, it is believed, previously appeared in the literature. The spare capacity network flow model uses a node-arc formulation while others have used an arc-path approach. The node-arc formulation is much more compact, and its special structure can be exploited in devising solution techniques. An original algorithm, inspired by Benders' decomposition procedure and called the network cut algorithm, is developed to solve the spare capacity network flow model. Application of decomposition principles results in an algorithm that iterates between a pure integer master problem and a set of minimum cost network flow subproblems. The algorithm incorporates a branch-and-bound procedure to solve the master problem, and a pure network dual simplex optimizer to solve the subproblems. The network cut algorithm is much more efficient than directly solving either the continuous relaxation or the mixed integer version of the spare capacity network flow model.