This paper proposes a methodology for location of Base Stations of cellular radio networks in India with the objective of optimizing and automating the process of network planning. Operations of a large telecom operator in rural parts of India are studied. The Operator's network planning team currently uses a manual approach to identify locations for the Base Stations. In this study the Base Station location problem is modelled as a discrete facility location problem and methodology that would help deal with conflicting network planning objectives i.e. cost, signal quality and coverage is presented and the best strategy under budget uncertainty is also explored. The model is run on data pertaining to one of the large States in India using CPLEX 10.0 [25] and OpenSolver [1]. Results indicate that, using the optimal approach, cost savings to the extent of 26% can be achieved. This is equivalent to a saving of INR 1 billion in the single State that is studied. Considering that the model can be replicated throughout the country, adoption of the proposed methodology can bring about substantial savings in the Operator's Base Station infrastructure costs.