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 consist in fixing an order for the satellites and determining their actual location by linear programming. In such procedures it is crucial to efficiently solve the very large number of arising special linear programs. We describe those linear preograms, 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, we generalize Cunninham's concept of strongly feasible bases to our case present a procedure based thereupon which prevents cycling. Computational experience with our algorithms subdtantiates our efficiency claims.