Premium
A generalized upper bounding approach to a communications network planning problem
Author(s) -
McCallum C. J.
Publication year - 1977
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230070102
Subject(s) - bounding overwatch , computer science , mathematical optimization , arc routing , routing (electronic design automation) , network planning and design , linear programming , mathematics , computer network , artificial intelligence
An important network optimization problem is to determine the routing of circuits and construction of additional are capacity in a communications network so as to satisfy forecasted circuit requirements at minimum cost. This paper considers the single‐time‐period version of the problem formulated as a linear program in the arc‐chain form. The special structure of this linear program is exploited to develop an efficient solution procedure. In particular, the generalized upper bounding technique devised by Dantzig and Van Slyke is applied. The computer implementation of the procedure is discussed and computational experience is reported. Brief mention is also made of certain extensions that are being pursued.