The objective of this study is to present some mathematical programming formulations and efficient solution methods which can be utilized in the topological design of communication networks. In consideration of the fact that many real-world communication networks are hierarchically structured, we concentrate the research interest on the design of two-level hierarchical networks. Unlike the conventional approaches of partitioning the global design problem into the design of backbone network and the design of local access networks, we adopt the unified approach resolving the two subproblems simultaneously.
First, we focus on the design of network whose embedded back-bone network is fully meshed and the local access networks attached to it are of star type. Two formulations, that is a quadratic 0-1 programming model and an equivalent mixed 0-1 integer programming model are presented for this single-homing full-mesh net-work(SHFMN) design problem. Based on the observation that this problem can be viewed as a general version of the UFLP, a dual-based solution procedure is developed. To overcome the computational difficulty arising from the exponential number of side constraints in the linearized model, a method which generates the constraints one by one only when needed is devised. The performance of the proposed solution method is tested through computational experiments with a wide variety of sample problems.
Secondly, an extension of the SHFMN design problem to the situation where the secondary assignment of each user node is required is considered. In the same manner as the SHFMN design problem, this dual-homing full-mesh network(DHFMN) design problem is also formulated as a quadratic 0-1 programming model and transformed into a mixed 0-1 integer programming model. A modified dual-based solution method which exploits the structure of the linearized model is developed. Through the computational experiments, the performance of the solution procedure is tested and peculiar properties of the DHFMN design problem are also investigated.
Finally, other classes of the network design problems where the configuration of the embedded backbone network is not limited to the full-mesh are considered. It is shown that under the assumption that clusters of user nodes and a configuration of the backbone network are given, these problems can be transformed into the SHFMN or the DHFMN design problem.
