×

Frequency assignment in mobile radio systems using branch-and-cut techniques. (English) Zbl 0961.90051

Summary: We present a new exact method to plan frequency assignment for mobile radio systems in a geographical region. Frequencies are to be assigned to ‘cells’ so that the required service is performed under the particular constraint that the overall noise-signal ratio, related to interference, should not exceed a given level for each cell-frequency pair. This NP-hard problem is formulated as an integer linear program and solved by an exact branch-and-cut technique, based on strong cutting planes. We start with very few constraints and use separation procedures to detect the violated constraints. The method and its implementation are tested on a library containing 85 real-world instances provided by CSELT, a major research laboratory operating with TIM (one of the Italian mobile radio system managers). We report the exact solution of instances with up to 203 cells within acceptable computing time.

MSC:

90B80 Discrete location and assignment
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90B18 Communication networks in operations research

Software:

MINTO; CALMA
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] K. Aardal, A. Hipolito, C. van Hoesel, B. Jansen, C. Roos, T. Terlaky, EUCLID CALMA radio link frequency assignment project: A branch-and-cut algorithm for the frequency assignment problem, Technical Annex T-2.2.1 A, CALMA project, T.U. Eindhoven, T.U. Delft, February 1995; K. Aardal, A. Hipolito, C. van Hoesel, B. Jansen, C. Roos, T. Terlaky, EUCLID CALMA radio link frequency assignment project: A branch-and-cut algorithm for the frequency assignment problem, Technical Annex T-2.2.1 A, CALMA project, T.U. Eindhoven, T.U. Delft, February 1995
[2] Araki, K., Fundamental problems of nation-wide mobile radio telephone system, Rev. El. Comm. Lab., 16, 357-373 (1968)
[3] Borndörfer, R. A.; Eisenblätter, A.; Grötschel, M.; Martin, A., Frequency assignment in cellular phone networks, Annals of Operations Research, 76, 73-93 (1998) · Zbl 0895.90090
[4] Box, F., A heuristic technique for assigning frequencies to mobile radio nets, IEEE Transactions on Vehicular Technology, VT-27, 57-64 (1977)
[5] A. Caprara, M. Fischetti, Branch-and-Cut algorithms: an annotated bibliography, in: M. Dell’Amico, F. Maffioli, S. Martello (Eds.), Annotated Bibliographies in Combinatorial Optimization, Wiley, New York, 1997, pp. 45-63; A. Caprara, M. Fischetti, Branch-and-Cut algorithms: an annotated bibliography, in: M. Dell’Amico, F. Maffioli, S. Martello (Eds.), Annotated Bibliographies in Combinatorial Optimization, Wiley, New York, 1997, pp. 45-63 · Zbl 1068.90505
[6] Castelino, D.; Hurley, S.; Stephens, N., A tabu search algorithm for frequency assignment, Annals of Operations Research, 63, 301-319 (1996) · Zbl 0851.90094
[7] Dahl, G.; Jörnsten, K.; Lovnes, G.; Svaet, S., Graph optimization problems in connection with the management of mobile communication systems, Telecommunication Systems, 3, 319-339 (1995)
[8] M. Duque-Antón, D. Kunz, B.Rüber, Channel assignment for cellular radio using simulated annealing, IEEE Transactions on Vehicular Technology 42 (1993); M. Duque-Antón, D. Kunz, B.Rüber, Channel assignment for cellular radio using simulated annealing, IEEE Transactions on Vehicular Technology 42 (1993)
[9] M. Fischetti, C. Lepschy, G. Minerva, G. Romanin Jacur, E. Toto, Frequency assignment in mobile radio systems using branch-and-cut techniques, in: Proceedings of the AIRO’96 Meeting Perugia, 16-20 September 1996, pp. 312-314; M. Fischetti, C. Lepschy, G. Minerva, G. Romanin Jacur, E. Toto, Frequency assignment in mobile radio systems using branch-and-cut techniques, in: Proceedings of the AIRO’96 Meeting Perugia, 16-20 September 1996, pp. 312-314 · Zbl 0961.90051
[10] M. Fischetti, C. Lepschy, G. Minerva, G. Romanin Jacur, E. Toto, Frequency assignment in mobile radio systems using branch-and-cut techniques, Collected Abstracts of the ECCO X Meeting, Puerto de La Cruz, Tenerife, May 14-17 1997, pp. 22-22; M. Fischetti, C. Lepschy, G. Minerva, G. Romanin Jacur, E. Toto, Frequency assignment in mobile radio systems using branch-and-cut techniques, Collected Abstracts of the ECCO X Meeting, Puerto de La Cruz, Tenerife, May 14-17 1997, pp. 22-22
[11] A. Gamst, A resource allocation technique for FDMA systems, Philips GmbH Forschungslaboratorium Hamburg, 1988; A. Gamst, A resource allocation technique for FDMA systems, Philips GmbH Forschungslaboratorium Hamburg, 1988
[12] S.W. Halpern, Reuse partitioning in cellular systems, in: Proceedings of the 33rd IEEE Vehicular Technology Conferene, Toronto, 1983, pp. 322-327; S.W. Halpern, Reuse partitioning in cellular systems, in: Proceedings of the 33rd IEEE Vehicular Technology Conferene, Toronto, 1983, pp. 322-327
[13] Hovi, M., From cellular plan to a practical operating network. Mobile radio systems and techniques, IEEE Conference Publishing series, 238, 53-56 (1984)
[14] C. Hurkens, S. Tiourine, Upper and lower bounding techniques for frequency assignment problems, Technical Report, T.U. Eindhoven, July 1995; C. Hurkens, S. Tiourine, Upper and lower bounding techniques for frequency assignment problems, Technical Report, T.U. Eindhoven, July 1995
[15] S.U. Hurley, D.S. Thiel, A comparison of local search algorithms for radio link frequency assignment problems, in: Proceedings of the 11th Annual ACM Symposium on Applied Computing, February 1996, pp. 251-257; S.U. Hurley, D.S. Thiel, A comparison of local search algorithms for radio link frequency assignment problems, in: Proceedings of the 11th Annual ACM Symposium on Applied Computing, February 1996, pp. 251-257
[16] B. Jaumard, O. Marcotte, C. Meyer, Mathematical models and exact methods for channel assignment in cellular networks, Telecommunications Network Planning, Elsevier, Amsterdam, 1998, pp. 203-219; B. Jaumard, O. Marcotte, C. Meyer, Mathematical models and exact methods for channel assignment in cellular networks, Telecommunications Network Planning, Elsevier, Amsterdam, 1998, pp. 203-219
[17] M. Jünger, G. Reinelt, G. Rinaldi, The traveling salesman problem, in: M. Ball, T.L. Magnanti, C.L. Monma, G.L. Nemhauser (Eds.), Handbooks in Operations Research and Management Science, vol. 7, Network Models, North-Holland, Amsterdam, 1995, pp. 255-330; M. Jünger, G. Reinelt, G. Rinaldi, The traveling salesman problem, in: M. Ball, T.L. Magnanti, C.L. Monma, G.L. Nemhauser (Eds.), Handbooks in Operations Research and Management Science, vol. 7, Network Models, North-Holland, Amsterdam, 1995, pp. 255-330 · Zbl 0832.90118
[18] MacDonald, V. H., Advanced mobile phone service: The cellular concept, Bell System Technical Journal, 58, 15-41 (1979)
[19] G.L. Nemhauser, L.A. Wolsey, Integer and Combinatorial Optimization, Wiley, New York, 1990; G.L. Nemhauser, L.A. Wolsey, Integer and Combinatorial Optimization, Wiley, New York, 1990 · Zbl 0944.90001
[20] Padberg, M., On the facial structure of set packing polyhedra, Mathematical Programming, 5, 199-215 (1973) · Zbl 0272.90041
[21] Padberg, M.; Rinaldi, G., A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems, SIAM Review, 33, 60-100 (1991) · Zbl 0734.90060
[22] C.A. Rypinski, Economic design of interference limited radiotelephone systems, in: Proceedings of the 33rd IEEE Vehicular Technology Conference, Toronto, 1983, pp. 332-340; C.A. Rypinski, Economic design of interference limited radiotelephone systems, in: Proceedings of the 33rd IEEE Vehicular Technology Conference, Toronto, 1983, pp. 332-340
[23] M.P. Savelsbergh, G.L. Nemhauser, Functional description of MINTO a mixed Integer Optimizer, Version 2.1. Technical Report, Georgia Institute of Technology, School of Industrial and System Engineering, Atlanta, 1995; M.P. Savelsbergh, G.L. Nemhauser, Functional description of MINTO a mixed Integer Optimizer, Version 2.1. Technical Report, Georgia Institute of Technology, School of Industrial and System Engineering, Atlanta, 1995
[24] S. Tiourine, C. Hurkens, J.K. Lenstra, Frequency assignment by local search, Technical Report T.U. Eindhoven, 1994; S. Tiourine, C. Hurkens, J.K. Lenstra, Frequency assignment by local search, Technical Report T.U. Eindhoven, 1994 · Zbl 1076.90515
[25] S. Tiourine, C. Hurkens, J.K. Lenstra, An overview of algorithmic approaches to frequency assignment problems, Technical Report T.U. Eindhoven, August 1995; S. Tiourine, C. Hurkens, J.K. Lenstra, An overview of algorithmic approaches to frequency assignment problems, Technical Report T.U. Eindhoven, August 1995
[26] Whitehead, J. F., Cellular system design an emerging engineering discipline, IEEE Communication Magazine, 24, 8-15 (1986)
[27] L.A. Wolsey, Faces of linear inequalities in 0-1 variables, Mathematical Programming 8 (1975) 165-178; L.A. Wolsey, Faces of linear inequalities in 0-1 variables, Mathematical Programming 8 (1975) 165-178 · Zbl 0314.90063
[28] Zoellner, J. A.; Beall, C. L., A breakthrough in spectrum conserving frequency assignment technology, IEEE Transactions on Electromagnetic Compatibility, EMC-19, 3, 313-319 (1977)
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.