Calculating solution-value bounds for a geostationary-satellite location problem (Q751998)

The astrophysical satellite location problem (SLP) is considered and a technique is developed for bounding its optimal solution. SLP deals with allotting orbital locations in the geostationary orbit to a number of satellites. The aim is to minimize the sum of the absolute deviations of the prescribed locations from the a priori specified desired locations, subject to service arc and electromagnetic interference constraints. The authors present this task as a special mixed integer programming problem and prove its NP-completeness. They derive four a priori bounds for the solution value. Under a mild condition each of these bounds dominates the bound found from the LP-relaxation. Most interesting is the bound based on the decomposition of SLP. Three decomposition schemes are proposed, and some computational results are reported. A by-product of the described bounding technique is a collection of valid inequalities that can be appended to SLP to strengthen its LP-relaxation.