An enumerative algorithm for the frequency assignment problem. (English) Zbl 1023.68004
Summary: We present an algorithm to solve the frequency assignment problem for mobile cellular systems and radio and television broadcasting. Frequencies must be assigned to transmitters in order to meet interference requirements so that the overall signal/noise ratio is satisfactory. The basic scheme is an exact enumerative method provided with fixing criteria to reduce the size of the instances. Larger instances are solved by applying the algorithm to suitable subinstances, eventually extending the solutions found. We were able to solve large real-life instances arising in radio broadcasting and mobile cellular systems. Computational results outperform previous results reported in the literature.
MSC:
| 68M10 | Network design and communication in computer systems |
References:
| [1] | K.I. Aardal, A. Hipolito, C.P.M. van Hoesel, G. Jansen, A branch-and-cut algorithm for the frequency assignment problem, http://ftp.win.tue.nl/pub/techreports/CALMA/index.html; K.I. Aardal, A. Hipolito, C.P.M. van Hoesel, G. Jansen, A branch-and-cut algorithm for the frequency assignment problem, http://ftp.win.tue.nl/pub/techreports/CALMA/index.html |
| [2] | A. Bouju, J.F. Boyce, C.H.D. Dimitropoulos, G. vom Scheidt, J.G. Taylor, Tabu search for the radio links frequency assignment problem, in: Proceedings of the Conference on Applied Decision Technologies: Modern Heuristic Methods, Brunel University, 1995, pp. 233-250.; A. Bouju, J.F. Boyce, C.H.D. Dimitropoulos, G. vom Scheidt, J.G. Taylor, Tabu search for the radio links frequency assignment problem, in: Proceedings of the Conference on Applied Decision Technologies: Modern Heuristic Methods, Brunel University, 1995, pp. 233-250. |
| [3] | Castelino, D. J.; Hurley, S.; Stephens, N. M., A tabu search algorithm for frequency assignment, Ann. Oper. Res., 63, 301-319 (1996) · Zbl 0851.90094 |
| [4] | Costa, D., On the use of some known methods for T-colourings of graphs, Ann. Oper. Res., 41, 343-358 (1993) · Zbl 0771.68089 |
| [5] | W. Crompton, S. Hurley, N.M. Stephens, A parallel genetic algorithm for frequency assignment problems, in: Proceedings of the IMACS/IEEE Conference on Signal Processing, Robotics and Neural Networks, Lille, France, 1994, pp. 81-84.; W. Crompton, S. Hurley, N.M. Stephens, A parallel genetic algorithm for frequency assignment problems, in: Proceedings of the IMACS/IEEE Conference on Signal Processing, Robotics and Neural Networks, Lille, France, 1994, pp. 81-84. |
| [6] | Duque-Anton, M.; Kunz, D.; Ruber, B., Channel assignment for cellular radio using simulated annealing, IEEE Trans. Vehicular Technol., 42, 14-21 (1993) |
| [7] | M. Fischetti, C. Lepschy, G. Minerva, G. Romanin-Jacur, E. Toto, Frequency assignment in mobile radio systems using branch-and-cut techniques, Eur. J. Op. Res. 123 (2000) 241-255.; M. Fischetti, C. Lepschy, G. Minerva, G. Romanin-Jacur, E. Toto, Frequency assignment in mobile radio systems using branch-and-cut techniques, Eur. J. Op. Res. 123 (2000) 241-255. · Zbl 0961.90051 |
| [8] | Gamst, A., Some lower bounds for a class of frequency assignment problems, IEEE Trans. Vehicular Technol., 35, 8-14 (1986) |
| [9] | Glover, F.; Parker, M.; Ryan, J., Coloring by tabu branch and bound, (Johnson, D. S.; Trick, M. A., Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge. Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, Discrete Mathematics and Theoretical Computer Science, Vol. 26 (1996), American Mathematical Society: American Mathematical Society Providence, RI), 285-307 · Zbl 0864.90120 |
| [10] | Goldberg, M. K.; Rivenburgh, R. D., Constructing cliques using restricted backtracking, (Johnson, D. S.; Trick, M. A., Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge. Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, Discrete Mathematics and Theoretical Computer Science, Vol. 26 (1996), American Mathematical Society: American Mathematical Society Providence, RI), 285-307 · Zbl 0859.68067 |
| [11] | Hale, W. K., Frequency assignment: theory and applications, Proc. IEEE, 68, 1497-1514 (1980) |
| [12] | S. Hurley, S.U. Thiel, D.H. Smith, A comparison of local search algorithms for radio link frequency assignment problems, in: ACM Symposium on Applied Computing, Philadelphia, 1996, pp. 251-257.; S. Hurley, S.U. Thiel, D.H. Smith, A comparison of local search algorithms for radio link frequency assignment problems, in: ACM Symposium on Applied Computing, Philadelphia, 1996, pp. 251-257. |
| [13] | J. Janssen, K. Kilakos, Polyhedral analysis of channel assignment problems: (I) Tours, Technical Report CDAM-96-17, London School of Economics, and on 1996.; J. Janssen, K. Kilakos, Polyhedral analysis of channel assignment problems: (I) Tours, Technical Report CDAM-96-17, London School of Economics, and on 1996. |
| [14] | Kim, S.; Kim, S.-L., A two phase algorithm for frequency assignment in cellular mobile systems, IEEE Trans. Vehicular Technol., 43, 542-548 (1994) |
| [15] | Kunz, D., Channel assignment for cellular radio using neural networks, IEEE Trans. Vehicular Technol., 40, 1, 188-193 (1991) |
| [16] | R. Leese, Tiling methods for channel assignment in radio communication networks, in: Proceedings of the Third ICIAM Congress, 1996.; R. Leese, Tiling methods for channel assignment in radio communication networks, in: Proceedings of the Third ICIAM Congress, 1996. · Zbl 0925.90177 |
| [17] | G.D. Lochtie, M.J. Mehler, Channel assignment using a subspace approach to neural networks, IEE Antennas Propagation (1995) 296-300.; G.D. Lochtie, M.J. Mehler, Channel assignment using a subspace approach to neural networks, IEE Antennas Propagation (1995) 296-300. |
| [18] | Sewell, E. C., An improved algorithm for exact graph coloring, (Johnson, D. S.; Trick, M. A., Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge. Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, Discrete Mathematics and Theoretical Computer Science, Vol. 26 (1996), American Mathematical Society: American Mathematical Society Providence, RI), 359-372 · Zbl 0866.05025 |
| [19] | Smith, D. H.; Hurley, S., Bounds for the frequency assignment problem, Discrete Math., 167/168, 571-582 (1997) · Zbl 0873.05041 |
| [20] | Smith, D. H.; Hurley, S.; Thiel, S. U., Improving heuristics for the frequency assignment problem, Eur. J. Oper. Res., 107, 76-86 (1998) · Zbl 0943.90056 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
