Designing satellite communication networks by zero—one quadratic programming
- 1 July 1989
- Vol. 19 (4), 427-450
- https://doi.org/10.1002/net.3230190404
Abstract
In satellite communications networks, distinctive facilities called homing stations perform special transmission functions. Local demand nodes clustered around each homing station communicate with each other via a local switch at the homing station; demand nodes in different cluster communicate with each other via satellite earth stations at the homing stations. Designing such a communication network requires choices on the locations of the earth stations and on the assignments of demand nodes to the local clusters at the earth stations. We formulate this problem as a zero-one quadratic facility location problem and transform it into an equivalent zero-one integer linear program. Computational experience on real data shows that a branch and bound procedure is effective in solving problems with up to 40 demand nodes (major cities) and that the solutions that this algorithm finds improve considerably upon management generated solutions. We also show that a greedy add heuristic, as implemented on an IBM PC, consistently generates optimal or near-optimal solutions.Keywords
This publication has 29 references indexed in Scilit:
- Lagrangian relaxation for the star‐star concentrator location problem: Approximation algorithm and boundsNetworks, 1985
- A numerical investigation of the impact of uncertain demand and varying risk preferences on the pricing and capacity decisions of transportation firms: The case of airlinesTransportation Research Part B: Methodological, 1983
- Centralized teleprocessing network designNetworks, 1983
- Extensions to a Lagrangean relaxation approach for the capacitated warehouse location problemEuropean Journal of Operational Research, 1983
- Topological design of centralized computer networks—formulations and algorithmsNetworks, 1982
- The Design of the XMP Linear Programming LibraryACM Transactions on Mathematical Software, 1981
- A model for the blocking of trainsTransportation Research Part B: Methodological, 1980
- Models for rail transportationTransportation Research Part A: General, 1980
- An Improved Algorithm for the Capacitated Facility Location ProblemJournal of the Operational Research Society, 1978
- Large-Scale Network Topological OptimizationIEEE Transactions on Communications, 1977