Unidirectional loop network layout by a LP heuristic and design of telecommunications networks

Abstract

In this paper, we present a new linear programming-based heuristic procedure for optimal design of the unidirectional loop network layout problem. The heuristic procedure employs a linear programming formulation and solves the problem using the flow matrix of the unidirectional loop problem. To find an optimal solution, one can either generate all possible solutions or use a branch-and-bound procedure. But, both above methods require very high computational time and computer memory for larger problems. The heuristic developed in this paper is quite fast and obtains near optimal solutions. The heuristic procedure was tested on 16 different problems selected from the literature. The results showed that in most cases optimal—and in a few cases near optimal—solutions were obtained with very little computational time. Several examples are discussed. We also demonstrate that the above problem formulation and approach can be used to solve a special class of telecommunication networks where a set of computers (or processors) are attached by unidirectional point-to-point links around a loop.