A standard model, suitable for planning purposes, identifies a wireless network with a set of transmitting and receiving antennas scattered over a territory. Such antennas are characterized by a position (geographical coordinates and elevation) and by a number of radio-electrical parameters. The network design process consists in establishing locations and suitable radio-electrical parameters of the antennas. The resulting network is evaluated by means of two basic performance indicators: (1) network coverage, that is the quality of the wanted signals perceived in the target region and (2) network capacity, that is the ability of the network to meet traffic demand. On the basis of quality requirements and projected demand patterns, suitable target thresholds are established for both indicators. In principle, coverage and capacity targets should be pursued simultaneously, as they both depend on the network configuration. However, to handle large real-life instances, conventional network planning resorts to a natural decomposition approach, which consists in performing coverage and capacity planning at different stages. In particular, the network is designed by first placing and configuring the antennas to ensure the coverage of a target area, and then by assigning a suitable number of frequencies to meet (projected) capacity requirements. The final outcome can be simulated and evaluated by an expert, and the whole process can be repeated until a satisfactory result is obtained (Figure 1). Future change in demand patterns can be met by increasing sectorization (i.e., mounting additional antennas in a same site), by selecting new sites, and by assigning additional transmission frequencies).
The network planning process requires an adequate representation of the territory. In the past years, the standard approach was to subdivide the territory into equally sized hexagons and basic propagation laws were implemented to calculate field strengths. By straightforward analytical computations, these simplified models could provide the (theoretical) position of the antennas and their transmission frequencies. Unfortunately, the approximations introduced by this approach were in most cases unacceptable for practical planning, as the model does not take into account several fundamental factors (e.g., orography of target territories, equipment configurations, actual availability of frequencies and of geographical sites to accommodate antennas, etc.). Furthermore, the extraordinary increase of wireless communication quickly resulted in extremely large networks and congested frequency spectrum, and asked for a better exploitation of the available band. It was soon apparent that effective automatic design algorithms were necessary to handle large instances of complex planning problems, and to improve the exploitation of the scarce radio resources. These algorithms were provided by mathematical optimization. Indeed, already in the early 1980s, it was recognized that the frequency assignment performed at the second stage of the planning process is equivalent to the Graph Coloring Problem (or to its generalizations). The graph coloring problem consists in assigning a color (= frequency) to each vertex (= antenna) of a graph so that adjacent vertices receive different colors and the number of colors is minimum. The graph G = (V, E) associated with the frequency assignments of a wireless network is called interference graph, since edge uv 
E represents interference between nodes u V and v V and implies that u and v cannot be assigned the same frequency. The graph coloring problem is one of the most known and well studied topics in combinatorial optimization. A remarkable number of exact and heuristic algorithms have been proposed over the years to obtain optimal or suboptimal colorings. Some of these methods were immediately at hand to solve the frequency assignment problem.
E represents interference between nodes u V and v V and implies that u and v cannot be assigned the same frequency. The graph coloring problem is one of the most known and well studied topics in combinatorial optimization. A remarkable number of exact and heuristic algorithms have been proposed over the years to obtain optimal or suboptimal colorings. Some of these methods were immediately at hand to solve the frequency assignment problem.
The development of mathematical optimization methods triggered the introduction of more accurate representations of the target territories. In particular, also inspired by standard Quality-of-Service (QoS) evaluation methodologies, the coarse hexagonal cells were replaced with (the union of) more handy geometrical entities, namely the demand nodes introduced by Tutschku, and with the now universally adopted testpoints (TP). In the TP model, a grid of approximately squared cells is overlapped to the target area. Antennas are supposed to be located in the center of testpoints: all information about customers and QoS in a TP, such as traffic demand and received signals quality, are aggregated into single coefficients. The TP model allows for smarter representations of the territory, of the actual antennas position, of the signal strengths, and of the demand distributions. This in turn permits a better evaluation of the QoS and, most important, makes it possible to construct more realistic interference graphs, thus leading to improved frequency assignments. Indeed, by means of effective coloring algorithms, it was possible to improve the design of large real-life mobile networks and also of analogue and digital broadcasting networks.
Finally, basing on the TP model, it was also possible to develop accurate models and effective optimization algorithms to accomplish the first stage of the planning process, namely the coverage phase, to establish suitable positions and radio-electrical parameters for the antennas of a wireless network.
In recent years, thanks to the development of more effective optimization techniques and to the increase of computational power, a number of models integrating coverage and capacity planning have been developed and applied to the design of global system for mobile (GSM) , universal mobile telecommunication system (UMTS), Analog and Digital Video Broadcasting networks.
