Topological design of a two-level network with ring-star configuration. (English) Zbl 0771.90041
Summary: This paper deals with the topological design of a hierarchical two-level network where the upper-level hub network is of ring type and the lower- level local access networks are of star-type. The problem is modeled as a mixed 0-1 integer programming the special structure of which is exploited for the development of a dual-based lower bounding procedure. A heuristic procedure is developed to construct a primal feasible solution from the dual solution obtained by the dual procedure. The performance of our method is well demonstrated by the computational experiments conducted with a variety of test problems ranging up to 20 hub nodes and 50 user nodes.
MSC:
| 90B18 | Communication networks in operations research |
| 90C11 | Mixed integer programming |
| 90C09 | Boolean programming |
| 90-08 | Computational methods for problems pertaining to operations research and mathematical programming |
References:
| [1] | Balakrishnan, A.; Magnanti, T. L.; Wong, R. T., A dual-ascent procedure for large-scale uncapacitated network design, Ops Res., 37, 716-740 (1989) · Zbl 0681.90083 |
| [2] | Balas, E., The prize collecting traveling salesman problem, Networks, 19, 621-636 (1989) · Zbl 0676.90089 |
| [3] | Chung, S. H.; Myung, Y. S.; Tcha, D. W., Optimal design of a distributed network with a two-level hierarchical structure, Eur. J. Opl Res., 62, 105-115 (1992) · Zbl 0758.90072 |
| [4] | Clapp, G. H.; Singh, M.; Karr, S., Metropolitan area network architecture and services, (Proc. IEEE Globecom ’88 (November 1988)), 1246-1258 |
| [5] | Current, J. R.; Schilling, D. A., The covering salesman problem, Transportation Sci., 23, 208-213 (1989) · Zbl 0682.90092 |
| [6] | Erlenkotter, D., A dual based procedure for uncapacitated facility location, Ops Res., 26, 992-1009 (1978) · Zbl 0422.90053 |
| [7] | Gavish, B.; Pirkul, H., Computer and database location in distributed computer systems, IEEE Trans. Comput., C-35, 583-590 (1986) |
| [8] | Helme, M. P.; Magnanti, T. L., Designing satellite communication networks by zero-one quadratic programming, Networks, 19, 427-450 (1989) · Zbl 0669.90075 |
| [9] | Kim, J. G.; Tcha, D. W., Optimal design of a two-level hierarchical network with tree-star configuration, Computers & IE, 22, 273-281 (1992) |
| [10] | Langevin, A.; Soumis, F.; Desrosiers, J., Classification of traveling salesman problem formulations, OR Lett., 9, 127-132 (1990) · Zbl 0697.90057 |
| [11] | (Lawler, E. L.; Lenstra, J. K.; Kan, A. H.G. Rinnooy; Shmoys, D. B., The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization (1987), Wiley: Wiley Chichester) · Zbl 0562.00014 |
| [12] | Leung, J. M.Y.; Magnanti, T. L.; Singhal, V., Routing in point-to-point delivery systems: formulations and solution heuristics, Transportation Sci., 24, 245-260 (1990) · Zbl 0723.90019 |
| [13] | Magnanti, T. L.; Wong, R. T., Network design and transportation planning: models and algorithms, Transportation Sci., 18, 1-55 (1984) |
| [14] | Mirzaian, A., Lagrangian relaxation for the star-star concentrator location problem: approximation algorithm and bounds, Networks, 15, 1-20 (1985) · Zbl 0579.94031 |
| [15] | Morreale, P. A.; Campbell, G. M., Metropolitan area networks, IEEE Spectrum, 27, 40-42 (1990) |
| [16] | Ong, H. L., Approximate algorithm for the traveling purchaser problem, OR Lett., 1, 201-205 (1982) · Zbl 0504.90078 |
| [17] | Padberg, M.; Rinaldi, G., Optimization of a 532-city symmetric traveling salesman problem by branch and cut, OR Lett., 6, 1-7 (1987) · Zbl 0618.90082 |
| [18] | Sriram, R.; Garfinkel, R. S., Locating interactive hub facilities, (Proc. 1st ORSA Telecommunications SIG Conference. Proc. 1st ORSA Telecommunications SIG Conference, Florida, March (1990)), 227-238 |
| [19] | Vernekar, A.; Anandalingam, G.; Dorny, C. N., Optimization of resource location in hierarchical computer networks, Computers OR, 17, 375-388 (1990) · Zbl 0692.68044 |
| [20] | Vob, S., Designing special communication networks with the traveling purchaser problem, (Proc. 1st ORSA Telecommunications SIG Conference. Proc. 1st ORSA Telecommunications SIG Conference, Florida, March (1990)), 106-110 |
| [21] | Wong, R. T., A dual ascent approach for Steiner tree problem on a directed graph, Math. Prog., 28, 271-287 (1984) · Zbl 0532.90092 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
