Minimum span frequency assignment problem on triangular lattices

This paper considers the Minimum Span Frequency Assignment Problem with Interference Graph on Triangular Grid (MSFAP-TG), a special case of the Minimum Span Frequency/Channel Assignment (MSFAP) for cellular systems and optical networks. The MSFAP-TG is interesting in its own right and thus worth studying. In this paper, we propose strong integer programming formulations for the MSFAP-TG and present polyhedral results on these formulations. In solving the MSFAP-TG, we implement these integer programs to obtain exact solutions. We also develop a heuristic for obtaining feasible solutions and upper bounds for the problems. With the use of these upper bounds, and a simple lower bound, the computation time of the exact algorithm can be improved substantially. The heuristic turns out to be quite good in terms of the quality of upper bounds and is extremely efficient in computation time. Last of all, we present new concepts for tackling large scale MSFAP-TGs.