Wise resource allocation is necessary to increase the quality of service (QoS), the system capacity, the network performance, and also decrease the power consumption and connection cost. This paper, first, investigates the located global system for mobile (GSM) network in a region of Tehran province in Iran as a case of study and then proposes a novel approach to minimize the connection cost among different parts and components of the GSM network while considering our network practical constraints. The approach of this paper can also be used for the other network planning problems such as the universal mobile telecommunication system (UMTS) in the third generation of the mobile systems. In order to find an optimal solution for the total network connections cost, we use mathematical programming based on mixed integer programming (MIP) algorithm to minimize the connection cost. At the end, simulation and practical results show us that our proposed algorithm decreases the connection cost and improve the QoS of the GSM network.