On the selection of primary paths for a communication network

Abstract

This paper deals with a non-bifurcated flow assignment problem in communication networks in which communication paths are limited to a set of pre-selected paths for each node pair. This problem is formulated as a mixed 0-1 linear model with multiple-choice constraints. A heuristic algorithm is presented, which takes a straightforward iterative approach, conceptually similar to that of the Simplex method, for finding the characterized local optimal solution. Several subprocedures which exploit the special structure of the model are included to make the algorithm computationally efficient. The relaxed linear programming model is used for the analysis of the algorithm, and its solution is found to be a tight lower bound. Applications of the algorithm to problems with other performance criteria are also suggested. Computational experience obtained thus far indicates that the algorithm almost always guarantees a quick convergence to a good suboptimal solution. © 1985.