Frequency planning and ramifications of coloring

Andreas Eisenblätter ; Martin Grötschel ; Arie M.C.A. Koster

Discussiones Mathematicae Graph Theory, Tome 22 (2002), p. 51-88 / Harvested from The Polish Digital Mathematics Library

Résumé

This paper surveys frequency assignment problems coming up in planning wireless communication services. It particularly focuses on cellular mobile phone systems such as GSM, a technology that revolutionizes communication. Traditional vertex coloring provides a conceptual framework for the mathematical modeling of many frequency planning problems. This basic form, however, needs various extensions to cover technical and organizational side constraints. Among these ramifications are T-coloring and list coloring. To model all the subtleties, the techniques of integer programming have proven to be very useful.The ability to produce good frequency plans in practice is essential for the quality of mobile phone networks. The present algorithmic solution methods employ variants of some of the traditional coloring heuristics as well as more sophisticated machinery from mathematical programming. This paper will also address this issue.Finally, this paper discusses several practical frequency assignment problems in detail, states the associated mathematical models, and also points to public electronic libraries of frequency assignment problems from practice. The associated graphs have up to several thousand vertices and range form rather sparse to almost complete.

Détail

Publié le : 2002-01-01

Zbl 1055.05147

EUDML-ID : urn:eudml:doc:270645

Bibliographie

[000] [1] K.I. Aardal, A. Hipolito, C.P.M. van Hoesel and B. Jansen, A branch-and-cut algorithm for the frequency assignment problem, Research Memorandum 96/011 (Maastricht University, 1996). Available at http://www.unimaas.nl/~svhoesel/.

[001] [2] K.I. Aardal, C.P.M. van Hoesel, A.M.C.A. Koster, C. Mannino and A. Sassano, Models and solution techniques for frequency assignment problems, ZIB Report 01-40 (Konrad-Zuse-Zentrum, Berlin, 2001). Available at http://www.zib.de/PaperWeb/abstracts/ZR-01-40. | Zbl 1157.90005

[002] [3] K.I. Aardal, C.A.J. Hurkens, J.K. Lenstra and S.R. Tiourine, Algorithms for frequency assignment: the CALMA project, to appear in Operations Research. | Zbl 1163.90579

[003] [4] S.M. Allen, D.H. Smith and S. Hurley, Lower bounding techniques for frequency assignment, Discrete Math. 197/198 (1999) 41-52 | Zbl 0956.90057

[004] [5] L.G. Anderson, A simulation study of some dynamic channel assignment algorithms in a high capacity mobile telecommunications system, IEEE Transactions on Communications 21 (1973) 1294-1301, doi: 10.1109/TCOM.1973.1091583.

[005] [6] D. Applegate, R. Bixby, V. Chvátal and W. Cook, On the solution of traveling salesman problems, in: Proceedings of the International Congress of Mathematicians Berlin 1998, volume III of Documenta Mathematica, DMV, 1998. | Zbl 0904.90165

[006] [7] G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela and M. Protasi, Complexity and Approximation: combinatorial optimization problems and their approximability properties (Springer-Verlag, 1999). | Zbl 0937.68002

[007] [8] M. Bellare, O. Goldreich and M. Sudan, Free bits, pcps and non-approximability-towards tight results, SIAM Journal on Computing 27 (1998) 804-915, doi: 10.1137/S0097539796302531. | Zbl 0912.68041

[008] [9] H.P. van Benthem, GRAPH generating radio link frequency assignment problems heuristically (Master's thesis, Delft University of Technology, 1995).

[009] [10] M. Biró, M. Hujter and Zs. Tuza, Precoloring extension. I: interval graphs, Discrete Math. 100 (1992) 267-279, doi: 10.1016/0012-365X(92)90646-W.

[010] [11] R. Borndörfer, A. Eisenblätter, M. Grötschel and A. Martin, Frequency assignment in cellular phone networks, Annals of Operations Research 76 (1998) 73-93, doi: 10.1023/A:1018908907763. | Zbl 0895.90090

[011] [12] F. Box, A heuristic technique for assigning frequencies to mobile radio nets, IEEE Transactions on Vehicular Technology 27 (1978) 57-74, doi: 10.1109/T-VT.1978.23724.

[012] [13] D. Brélaz, New methods to color the vertices of a graph, Communications of the ACM 22 (1979) 251-256, doi: 10.1145/359094.359101. | Zbl 0394.05022

[013] [14] S. Burer, R.D.C. Monteiro and Y. Zhang, Interior-point algorithms for semidefinite programming based on a nonlinear programming formulation, Technical Report TR 99-27, Department of Computational and Applied Mathematics, Rice University, Houston, Texas 77005, Dec. 1999. | Zbl 1006.90060

[014] [15] A. Caminada, CNET France Telecom frequency assignment benchmark, URL: http://www.cs.cf.ac.uk/User/Steve.Hurley/f_bench.htm, 2000

[015] [16] K.-N. Chang and S. Kim, Channel allocation in cellular radio networks, Computers and Operations Research 24 (1997) 849-860, doi: 10.1016/S0305-0548(96)00098-6. | Zbl 0891.90166

[016] [17] D. Costa, On the use of some known methods for t-colourings of graphs, Annals of Operations Research 41 (1993) 343-358, doi: 10.1007/BF02023000. | Zbl 0771.68089

[017] [18] M.B. Cozzens and F.S. Roberts, T-colorings of graphs and the channel assignment problem, Congr. Numer. 35 (1982) 191-208.

[018] [19] G. Dueck and T. Scheuer, Threshold accepting: a general purpose optimization algorithm appearing superior to simulated annealing, J. Computational Physics (1990) 161-175, doi: 10.1016/0021-9991(90)90201-B. | Zbl 0707.65039

[019] [20] A. Eisenblätter, Frequency Assignment in GSM Networks: Models, Heuristics, and Lower Bounds (Cuvillier Verlag, 2001).

[020] [21] A. Eisenblätter and A.M.C.A, Koster, FAP web-A website devoted to frequency assignment, URL: http://fap.zib.de, 2000.

[021] [22] P. Erdős, A.L. Rubin and H. Taylor, Choosability in graphs, Congr. Numer. 26 (1979) 125-157.

[022] [23] M. Fischetti, C. Lepschy, G. Minerva, G. Romanin-Jacur and E. Toto, Frequency assignment in mobile radio systems using branch-and-cut techniques, European Journal of Operational Research 123 (2000) 241-255, doi: 10.1016/S0377-2217(99)00254-4. | Zbl 0961.90051

[023] [24] A. Frieze and M. Jerrum, Improved Approximation Algorithms for MAX k-CUT and MAX BISECTION, Algorithmica 18 (1997) 67-81, doi: 10.1007/BF02523688. | Zbl 0873.68078

[024] [25] M. Grötschel, L. Lovász and A. Schrijver, Polynomial algorithms for perfect graphs, Annals of Discrete Math. 21 (1984) 325-356.

[025] [26] M. Grötschel, L. Lovász and A. Schrijver, Geometric Algorithms and Combinatorial Optimization (Springer-Verlag, 1988). | Zbl 0634.05001

[026] [27] W.K. Hale, Frequency assignment: Theory and applications, Proceedings of the IEEE 68 (1980) 1497-1514, doi: 10.1109/PROC.1980.11899.

[027] [28] M. Hellebrandt and H. Heller, A new heuristic method for frequency assignment, Technical Report TD(00) 003, COST 259 (Valencia, Spain, Jan, 2000).

[028] [29] C. Helmberg, SBmethod - A C++ implementation of the spectral bundle method, manuel to version 1,1, Technical Report 00-35, Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB) (Berlin, Germany, 2000).

[029] [30] C. Helmberg, Semidefinite programming for combinatorial optimization, Technical Report 00-34, Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB) (Berlin, Germany, 2000), Habilitation TU Berlin.

[030] [31] S. Hurley, D.H. Smith and S.U. Thiel, FASoft: A system for discrete channel frequency assignment, Radio Science 32 (1997) 1921-1939, doi: 10.1029/97RS01866.

[031] [32] J. Janssen and K. Kilakos, Polyhedral analysis of channel assignment problems: (i) tours, Technical Report CDAM-96-17 (London School of Economics, 1996).

[032] [33] J. Janssen and K. Kilakos, An optimal solution to the ``Philadelphia'' channel assignment problem, IEEE Transactions on Vehicular Technology 48 (3) (1999) 1012-1014, doi: 10.1109/25.765037.

[033] [34] B. Jaumard, O. Marcotte and C. Meyer, Mathematical models and exact methods for channel assignment in cellular networks, in: B. Sansáo and P. Soriano, eds, Telecommunications Network Planning, Chapter 13 (Kluwer Academic Publishers, Boston, 1999) 239-255, doi: 10.1007/978-1-4615-5087-7₁3.

[034] [35] D.S. Johnson, Worst case behaviour of graph colouring algorithms, Congr. Numer. 10 (1974) 513-527.

[035] [36] M. Jünger, G. Reinelt and G. Rinaldi, Network Models, Volume 7 of Handbooks in Operations Research and Management Science, Chapter The travelling salesman problem (Elsevier Science B.V., 1995) 225-330. | Zbl 0832.90118

[036] [37] D. Karger, R. Motwani and M. Sudan, Approximate graph coloring by semidefinite programming, Journal of the ACM 45 (2) (1998) 246-265, doi: 10.1145/274787.274791. | Zbl 0904.68116

[037] [38] M. Karoński, Random graphs, in: R. Graham, M. Grötschel and L. Lovász, eds, Handbook of Combinatorics, Volume 1, Chapter 6 (Elsevier Science B.V., 1995) 351-380. | Zbl 0845.05082

[038] [39] R.M. Karp, Reducibility among combinatorial problems, in: R.E. Miller and J.W. Thatcher, eds, Complexity of Computer Computations (Plenum Press, New York, 1972) 85-103.

[039] [40] A.W.J. Kolen, A genetic algorithm for frequency assignment, (Technical report, Maastricht University, 1999). Available at http://www.unimaas.nl/~akolen/.

[040] [41] A.M.C.A. Koster, Frequency Assignment-Models and Algorithms (PhD Thesis, Maastricht University, 1999). Available at http://www.zib.de/koster/thesis.html.

[041] [42] A.M.C.A, Koster, C.P.M. van Hoesel and A.W.J. Kolen, Lower bounds for minimum interference frequency assignment problems, Technical Report RM 99/026 (Maastricht University, 1999). Available at http://www.zib.de/koster/.

[042] [43] R. Mathar and J. Mattfeldt, Channel assignment in cellular radio networks, IEEE Transactions on Vehicular Technology 42 (1993) 647-656, doi: 10.1109/25.260746.

[043] [44] B.H. Metzger, Spectrum management technique, Fall 1970, Presentation at 38th National ORSA meeting (Detroit, MI).

[044] [45] R.A. Murphey, P.M. Pardalos and M.G.C. Resende, Frequency assignment problems, in: D.-Z. Du and P.M. Pardalos, eds, Handbook of combinatorial optimization, volume Supplement Volume A (Kluwer Academic Publishers, 1999). | Zbl 1253.90137

[045] [46] A. Raychaudhuri, Intersection Assignments, T-Colourings and Powers of Graphs (PhD Thesis, Rutgers University, 1985).

[046] [47] ROADEF challenge 2001. URL: http://www.prism.uvsq.fr/~ vdc/ROADEF/ CHALLENGES/2001/, 2000.

[047] [48] F.S. Roberts, On the mobile radio frequency assignment problem and the traffic light phasing problem, Annals of New York Academy of Sciences 319 (1979) 466-483, doi: 10.1111/j.1749-6632.1979.tb32824.x. | Zbl 0475.94021

[048] [49] F.S. Roberts, T-colorings of graphs: Recent results and open problems, Discrete Math. 93 (1991) 229-245, doi: 10.1016/0012-365X(91)90258-4. | Zbl 0751.05042

[049] [50] K.N. Sivarajan, R.J. McEliece and J.W. Ketchum, Channel assignment in cellular radio, in: Proceedings of the 39th IEEE Vehicular Technology Conference (1989) 846-850, doi: 10.1109/VETEC.1989.40173.

[050] [51] S. Stahl, n-tuple colorings and associated graphs, J. Combin. Theory 20 (B) (1976) 185-203. | Zbl 0293.05115

[051] [52] J.F. Sturm, Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones, Technical report, Communications Research Laboratory (McMaster University, Hamilton, Canada, 1998). Available at: http://www.unimaas.nl/~ sturm/.

[052] [53] B.A. Tesman, T-colorings, list T-colorings, and set T-colorings of graphs (PhD Thesis, Department of Mathematics, Rutgers University, 1989).

[053] [54] B.A. Tesman, Set T-colorings, Congr. Numer. 77 (1990) 229-242.

[054] [55] B.A. Tesman, List T-colorings, Discrete Applied Mathematics 45 (1993) 277-289, doi: 10.1016/0166-218X(93)90015-G.

[055] [56] B. Toft, Colouring, stable sets and perfect graphs, in: R. Graham, M. Grötschel and L. Lovász, eds, Handbook of Combinatorics, Volume 1, Chapter 4 (Elsevier Science B.V., 1995) 233-288. | Zbl 0844.05042

[056] [57] C. Valenzuela, S. Hurley and D.H. Smith, A permutation based genetic algorithm for minimum span frequency assignment, Lecture Notes in Computer Science 1498 (1998) 907-916, doi: 10.1007/BFb0056932.

[057] [58] V.G. Vizing, Critical graphs with given chromatic class (Russian), Diskret, Analiz 5 (1965) 9-17.

[058] [59] W. Wang and C.K. Rushforth, An adaptive local-search algorithm for the channel-assignment problem (CAP), IEEE Transactions on Vehicular Technology 45 (1996) 459-466, doi: 10.1109/25.533761.

[059] [60] J.A. Zoellner and C.L. Beall, A breakthrough in spectrum conserving frequency assignment technology, IEEE Transactions on Electromagnetic Compatiblity 19 (1977) 313-319, doi: 10.1109/TEMC.1977.303601.