Modeling the satellite placement problem as a network flow problem with one side constraint

The placement of telecommunication satellites in the geostationary orbit (GSO) gives rise to NP-hard optimization problems usually approached with iterative neighborhood (possibly tabu) search schemes. A typical iteration thereof consists in fixing an order for the satellites and determining their actual locations by linear programming. In such procedures it is crucial to efficiently solve the very large number of arising special linear programs. The authors describe those linear programs, characterize their duals as special network flow problems with one side constraint and then present an efficient network simplex method to solve them. Since these problems can be highly degenerate, the authors generalize Cunningham’s concept of strongly feasible bases to the present case and present a procedure based thereupon which prevents cycling. Computational experience with the algorithms substantiates the present efficiency claims.