Designing Satellite Communication Networks by Zero-One Quadratic Programming
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 clusters communicate wit...
| Main Authors: | , |
|---|---|
| Format: | Working Paper |
| Language: | en_US |
| Published: |
Massachusetts Institute of Technology, Operations Research Center
2004
|
| Online Access: | http://hdl.handle.net/1721.1/5376 |
| _version_ | 1811077655552851968 |
|---|---|
| author | Helme, Marcia P. Magnanti, Thomas L. |
| author_facet | Helme, Marcia P. Magnanti, Thomas L. |
| author_sort | Helme, Marcia P. |
| collection | MIT |
| description | 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 clusters 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 forty 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. |
| first_indexed | 2024-09-23T10:46:26Z |
| format | Working Paper |
| id | mit-1721.1/5376 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T10:46:26Z |
| publishDate | 2004 |
| publisher | Massachusetts Institute of Technology, Operations Research Center |
| record_format | dspace |
| spelling | mit-1721.1/53762019-04-10T10:36:15Z Designing Satellite Communication Networks by Zero-One Quadratic Programming Helme, Marcia P. Magnanti, Thomas L. 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 clusters 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 forty 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. 2004-05-28T19:36:28Z 2004-05-28T19:36:28Z 1987-01 Working Paper http://hdl.handle.net/1721.1/5376 en_US Operations Research Center Working Paper;OR 159-87 2195334 bytes application/pdf application/pdf Massachusetts Institute of Technology, Operations Research Center |
| spellingShingle | Helme, Marcia P. Magnanti, Thomas L. Designing Satellite Communication Networks by Zero-One Quadratic Programming |
| title | Designing Satellite Communication Networks by Zero-One Quadratic Programming |
| title_full | Designing Satellite Communication Networks by Zero-One Quadratic Programming |
| title_fullStr | Designing Satellite Communication Networks by Zero-One Quadratic Programming |
| title_full_unstemmed | Designing Satellite Communication Networks by Zero-One Quadratic Programming |
| title_short | Designing Satellite Communication Networks by Zero-One Quadratic Programming |
| title_sort | designing satellite communication networks by zero one quadratic programming |
| url | http://hdl.handle.net/1721.1/5376 |
| work_keys_str_mv | AT helmemarciap designingsatellitecommunicationnetworksbyzeroonequadraticprogramming AT magnantithomasl designingsatellitecommunicationnetworksbyzeroonequadraticprogramming |