A NOVEL BINARY PROGRAMMING APPROACH FOR OPTIMAL DESIGN OF CELLULAR MOBILE

Syed Zahid Ali

   The present paper deals with the problem of determining the minimum number of base stations required to cover a given radio network area, together with the associated cell size and the best topographical configurations. Existing solutions to this NP-Complete problem are based on the heuristic approaches but these do not guarantee convergence to a true globally optimal solution. In this paper, a strong binary programming formulation is developed for the problem and a special branch and cut algorithm is applied for obtaining guaranteed optimal solutions. The presented examples show that using the proposed techniques, it is possible to solve optimally fairly large-size network design problems for the GSM as well as CDMA based mobile radio cellular systems.

Keywords: network design, independent set, branch and cut algorithm, binary linear

[full-paper]