Designing satellite communication networks by zero-one quadratic programming. (English) Zbl 0669.90075
In satellite communication 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 clusters communicate with each other via satellite earth stations at the homing stations. Designing such a communication networks 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.
MSC:
| 90C09 | Boolean programming |
| 90C90 | Applications of mathematical programming |
| 90B10 | Deterministic network models in operations research |
| 90C20 | Quadratic programming |
| 65K05 | Numerical mathematical programming methods |
Keywords:
design; satellite communication networks; homing stations; zero-one quadratic facility location; branch and bound; near-optimal solutionsReferences:
| [1] | Akinc, Management Sci. 23 pp 585– (1977) |
| [2] | Assad, Transportation Res. 14A pp 205– (1980) · doi:10.1016/0191-2607(80)90017-5 |
| [3] | and , A composite algorithm for a concave-cost network flow problem. WP#1669–85, Sloan School of Management, M.I.T., Cambridge, MA (1985), to appear in Networks. |
| [4] | and , On Benders decomposition and a plant location problem. ARO-27, Mathematica, Princeton, NJ (1963). |
| [5] | Bilde, Ann. Discrete Math. 1 pp 78– (1977) |
| [6] | Bodin, Transportation Res. 14B pp 115– (1980) |
| [7] | Boorstyn, IEEE Trans. Communications COM-25 pp 29– (1977) |
| [8] | Christofides, Eur. J. Operational Res. 12 pp 19– (1983) |
| [9] | Cornuejols, Management Sci. 23 pp 789– (1977) |
| [10] | Crowder, Operations Res. 31 pp 803– (1983) |
| [11] | Davis, Naval Res. Logistics Q. 16 pp 331– (1969) · Zbl 0186.24905 · doi:10.1002/nav.3800160306 |
| [12] | Effroymson, Operations Res. 14 pp 361– (1966) |
| [13] | Erlenkotter, Operations Res. 26 pp 992– (1978) |
| [14] | Fourer, Math. Programming 33 pp 204– (1985) · Zbl 0579.90084 |
| [15] | and , Discrete Location Theory, John Wiley and Sons, New York (forthcoming). · Zbl 0718.00021 |
| [16] | and , Facility Layout and Locations: An Analytic Approach. Prentice-Hall, Englewood Cliffs, NJ (1974). |
| [17] | Gavish, Networks 12 pp 355– (1982) |
| [18] | Guignard, Math. Programming 17 pp 198– (1979) |
| [19] | and , Location on Networks: Theory and Algorithms. M.I.T. Press, Cambridge, MA (1979). |
| [20] | and , Designing Satellite Communication Networks by Zero-One Quadratic Programming. Working Paper OR 159–87, Operations Research Center, M.I.T., Cambridge, MA (1987). |
| [21] | Johnson, Operations Res. 33 pp 803– (1985) |
| [22] | Kershenbaum, Networks 13 pp 279– (1983) |
| [23] | Khumawala, Management Sci. 18 pp 718– (1972) |
| [24] | Kuehn, Management Sci. 9 pp 643– (1963) |
| [25] | , and , Bounding procedures for fixed charge, multicommodity network design problems. Working Paper, Detp. of Civil Engineering, M.I.T., Cambridge, MA (1984). |
| [26] | Polyhedral structure of capacited fixed charge problems and a problem in delivery route planning. Ph.D. Thesis, Dept. of Electrical Engineering and Computer Science, M.I.T., Cambridge, MA (1985). |
| [27] | , and , Routing in point-to-point delivery systems. Working Paper OR 174–88, Operations Research Center, M.I.T., Cambridge, MA (1988). |
| [28] | Luss, Operations Res. 30 pp 907– (1982) |
| [29] | Magnanti, Transportation Sci. 18 pp 1– (1984) |
| [30] | Manne, Management Sci. 11 pp 213– (1964) |
| [31] | Marsten, ACM Trans. Mathe. Software 7 pp 481– (1981) |
| [32] | , and , A cutting plane approach to the concentrator location problem. Working Paper (1984). |
| [33] | Mirzaian, Networks 15 pp 1– (1985) |
| [34] | Nauss, J. Operational Res. Soc. 29 pp 1195– (1978) |
| [35] | Powell, Transportation Res. 17A pp 471– (1983) |
| [36] | Premoli, Mathe. Programming 36 pp 210– (1986) |
| [37] | Sa, Operations Res. 17 pp 1005– (1969) |
| [38] | Integer Programming. Addison-Wesley, Reading, MA (1975). · Zbl 0319.90038 |
| [39] | Point-to-point package delivery systems. M.Sc. Thesis. Operations Research Center, M.I.T., Cambridge, MA (1984). |
| [40] | Spielberg, Operations Res. 17 pp 85– (1969) |
| [41] | Stollsteimier, J. Farm Econ. 45 pp 631– (1961) |
| [42] | Computer Networks. Prentice-Hall, Englewood Cliffs, NJ (1981). |
| [43] | Tansel, Management Sci. 29 pp 482– (1983) |
| [44] | Location and network design. In Combinatorial Optimization: Annotated Bibliographies ( and , eds.) Wiley-Interscience, New York (1985) pp. 127–147. |
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.
