frequency assignment problem

Solving the frequency assignment problem by using meta-heuristic methods

Ieee account.

• Change Username/Password
• Update Address

Purchase Details

• Payment Options
• Order History
• View Purchased Documents

Profile Information

• Communications Preferences
• Profession and Education
• Technical Interests
• US & Canada: +1 800 678 4333
• Worldwide: +1 732 981 0060
• Contact & Support
• About IEEE Xplore
• Accessibility
• Terms of Use
• Nondiscrimination Policy
• Privacy & Opting Out of Cookies

A not-for-profit organization, IEEE is the world's largest technical professional organization dedicated to advancing technology for the benefit of humanity. © Copyright 2024 IEEE - All rights reserved. Use of this web site signifies your agreement to the terms and conditions.

Academia.edu no longer supports Internet Explorer.

To browse Academia.edu and the wider internet faster and more securely, please take a few seconds to  upgrade your browser .

Enter the email address you signed up with and we'll email you a reset link.

• We're Hiring!
• Help Center

Download Free PDF

Models and solution techniques for frequency assignment problems

2003, A Quarterly Journal of Operations Research

Wireless communication is used in many different situations such as mobile telephony, radio and TV broadcasting, satellite communication, and military operations. In each of these situations a frequency assignment problem arises with application specific characteristics. Researchers have developed different modeling ideas for each of the features of the problem, such as the handling of interference among radio signals, the availability of frequencies, and the optimization criterion. This survey gives an overview of the models and methods that the literature provides on the topic. We present a broad description of the practical settings in which frequency assignment is applied. We also present a classification of the different models and formulations described in the literature, such that the common features of the models are emphasized. The solution methods are divided in two parts. Optimization and lower bounding techniques on the one hand, and heuristic search techniques on the other hand. The literature is classified according to the used methods. Again, we emphasize the common features, used in the different papers. The quality of the solution methods is compared, whenever possible, on publicly available benchmark instances.

Related topics

•   We're Hiring!
•   Help Center
• Find new research papers in:
• Health Sciences
• Earth Sciences
• Cognitive Science
• Mathematics
• Computer Science
• Academia ©2024

Frequency Assignment Problems

Cite this chapter.

• Robert A. Murphey 4 ,
• Panos M. Pardalos 5 &
• Mauricio G. C. Resende 6  

1481 Accesses

39 Citations

The term frequency assignment has been used to describe many types of problems which, quite often, have different modeling needs and objectives. These problems include:

Planning models for permanent spectrum allocation, licensing, and regulation which maximize utilization of all radio spectra [94].

Planning models for network design within a given allocation to include; aeronautical mobile, land mobile, maritime mobile, broadcast, land fixed (point-to-point) and satellite.

On-line algorithms for dynamically assigning frequencies to users within an established network. Of special interest here are land cellular mobile systems, where an enormous amount of research has been done. A paper by Katzela and Naghshineh [55] contains nearly 100 references to works just in cellular dynamic channel assignment.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save.

• Get 10 units per month
• Download Article/Chapter or eBook
• 1 Unit = 1 Article or 1 Chapter
• Cancel anytime
• Available as PDF
• Read on any device
• Instant download
• Own it forever
• Compact, lightweight edition
• Dispatched in 3 to 5 business days
• Free shipping worldwide - see info
• Durable hardcover edition

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Unable to display preview.  Download preview PDF.

Similar content being viewed by others

Algorithms for Solving Frequency Assignment Problem in Wireless Networks

Efficient Solution Methods for the Cumulative-Interference Channel Assignment Problem Using Integer Optimization and Constraint Programming

An exact algorithm for a resource allocation problem in mobile wireless communications.

K.I. Aardal, A. Hipolito, C.P.M. Van Hoesel, B. Jansen, C. Roos and T. Terlaky, A branch-and-cut algorithm for the frequency assignment problem, EUCLID CALMA Project ,Delft and Eindhoven Universities of Technology, The Netherlands, (1995)

Google Scholar  

E. Aarts and J. Korst, Simulated Annealing and Boltzman Machines: A Stochastic Approach To Combinatorial Optimization and Neural Computing , John Wiley and Sons (1989) .

I. Baybars, Optimal assignment of broadcasting frequencies, European Journal of Operations Research , Vol. 9, (1982) pp. 257–263.

Article   MATH   Google Scholar  

E. A. Bender and H. S. Wilf, A theoretical analysis of backtracking in the graph coloring problem, Journal of Algorithms 6 , (1985), pp. 275–282.

H.P. Benthem, GRAPH: Generating radio link frequency assignment problems heuristically, Master’s Thesis, Faculty of Technical Mathematics and Informatics, Delft University, Delft, The Netherlands, (1995).

H. van Benthem, A. Hipolito, B. Jansen, C. Roos, T. Terlaky and J. Warners, EUCLID CALMA technical report, GRAPH: a test case generator, generating radiolink frequency assignment problems heuristically, EUCLID CALMA Project , Delft and Eindhoven Universities of Technology, The Netherlands, (1995).

H. van Benthem, A. Hipolito, B. Jansen, C. Roos, T. Terlaky and J. Warners, GRAPH, a test problem generator for the radiolink frequency assignment problem, EUCLID CALMA Project Supplemental Report 2.3.2a :, Delft and Eindhoven Universities of Technology, The Netherlands, (1995).

L.A. Berry and D. H. Cronin, The spectrum cost of frequency distance rules, IEEE International Symposium on Electromagnetic Compatibility , (1983) pp. 75–78.

D.P. Bertsekas and R. G. Gallager, Data Networks , 2nd ed , (Prentice-Hall, 1992 ).

B. Bollobâs and A. J. Harris, List colorings of graphs, Graphs and Combinatoricsl, (1985) pp. 115–187

I. Bonias, T-colorings of complete graphs, Ph.D. Thesis, Department of Mathematics, Northeastern University, Boston, MA (1991).

A. Bouju, J.F. Boyce, C.H.D. Dimitropoulis, G. vom Scheidt, and J.G. Taylor, Tabu search for the radio link frequency assignment problem, Applied Decision Technologies , London [ADT951 , UNICOM Conference , (1995).

F. Box, A heuristic technique for assigning frequencies to mobile radio nets, IEEE Trans. Vehicular Technology , Vol. VT-27, (1978), pp. 57–74.

D. Brelaz, New methods to color the vertices of a graph, Communications ACM , Vol. 22 , (1979) pp. 251–256.

Article   MathSciNet   MATH   Google Scholar  

S.H. Cameron, The solution of the graph coloring problem as a set covering problem, IEEE Transactions on Electromagnetic Compatibility , Vol EMC-19, (1973) pp. 320–322.

F. Carmassi and L. Tornati, A theory of frequency assignment in broadcasting network planning, European Broadcast Union Technical Review , No. 198, (Apr. 1983) pp. 72–81.

D.J. Castelino, S. Hurley and N.M. Stephens, A Tabu search algorithm for frequency assignment, Annals of Operations Research , Vol 41, (1993), pp. 343–358.

Article   Google Scholar  

D. Castelino and N. Stephens, Tabu thresholding for the frequency assignment problem, Meta-Heuristics: Theory and Applications (Edited by I.H. Osman and J.P. Kelly ), Kluwer Academic Publishers 1996.

V. Chvâtal, Perfectly ordered graphs, Annals of Discrete Mathematics , 21 , (1984) pp. 63–65.

L.W. Couch, Modern Communications Systems: Principles and Practices , Prentice-Hall, Inc., (1995).

M.B. Cozzens and F.S. Roberts, T-colorings of graphs and the channel assignment problem, Congressus Numerantium ,Vol 35 (1982), pp. 191208.

M.B. Cozzens and F.S. Roberts, Double semiorders and double indifference graphs, SIAM Journal Algebraic Discrete Methods 3 (1982) pp. 566–583.

M.B. Cozzens and F.S. Roberts, Greedy algorithms for T-colorings of complete graphs and the meaningfulness of conclusions about them, Journal of Combinatorics , Information and System Sciences , Vol 16 No. 4, (1991), pp. 286–299.

MathSciNet   MATH   Google Scholar  

M.B. Cozzens and D.I. Wang, The general channel assignment problem, Congressus Numerantium , Vol 41 (1984), pp. 115–129.

MathSciNet   Google Scholar  

W. Crompton, S. Hurley and N.M. Stephens, Frequency assignment using a parallel genetic algorithm, Proceedings of Natural Algorithms in Signal Processing , (1993).

C.E. Dadson, J. Durkin and R.E. Martin, Computer prediction of field strength in the planning of radio systems, IEEE Trans. Vehicular Technology , Vol. VT-24, (1975), pp. 1–8.

D. de Werra and Y. Gay, Chromatic scheduling and frequency assignment, Discrete Applied Mathematics 49 , (1994) pp. 165–174.

J. P. Doignon, Threshold representations of multiple semiorders, SIAM Journal Algebraic Discrete Methods 8 (1987) pp. 77–84.

R.B. Eggleton, P. Erdös and D.K. Skilton, Coloring the real line, Journal of Combinatorial Theory , Series B , 39 , (1985), 86–100.

Eindhoven RLFAP Group, Radio link frequency assignment project, EUCLID CALMA Project Report 2.3.3 Local Search :, Eindhoven University of Technology, The Netherlands, (1995).

A. Eisenblätter, A frequency assignment problem in cellular phone networks (extended abstract), Network Design , Connectivity and Facility Location , DIMACS Series in Discrete Mathematics and Theoretical Computer Science , Vol. 35, American Mathematical Society (1997).

P. Erdös, A. L. Rubin and H. Taylor, Choosability in graphs, Congres-sus Numerantium 26 , (1979), pp. 125–157.

L.R. Foulds, Graph Theory Application , Springer-Verlag New York Inc., (1992).

R.A. Frazier, Compatibility and the frequency selection problem, IEEE Trans. Electromagnetic Compatibility ,Vol. EMC-17, (1975), pp. 248275.

D. R. Fulkerson and O.A. Gross, Incidence matrices and interval graphs, Pacific Journal of Math 15 , (1965) pp. 835–855.

Z. Füredi, J. R. Griggs and D.J. Kleitinan, Pair labellings with given distance, SIAM Journal of Discrete Mathematics 2 , (1989) pp. 491–499.

A. Gamst, Some lower bounds for a class of frequency assignment problems, IEEE transactions on vehicular technology , Vol. VT -35, No. 1 (Feb. 1986), pp. 8–14.

A. Gamst and K. Ralf, Computational complexity of some interference graphs, IEEE Transactions on Vehicular Technology , Vol 39 No. 2, (1990) pp. 140–149.

A. Gamst and W. Rave, On frequency assignment in mobile automatic telephone systems, GLOBCOM 82 , IEEE Global Telecommunications Conference , Vol 1 , (1982) pp. 309–315.

M. R. Garey and D. S. Johnson, Computers and Intractability , A Guide To The Theory of NP-Completeness , W.H. Freeman and Company, New York, NY (1979).

F. Glover, Tabu search - Part I. ORSA Journal on Computing 1 : 190206, 1989.

F. Glover, Tabu search–Part II. ORSA Journal on Computing 2 : 4–32, 1990.

F. Glover, Tabu Thresholding: Improved search strategies by non-monotonic search trajectories, ORSA Journal on Computing to appear.

D.E. Goldberg, Genetic Algorithms in Search , Optimization and Machine Learning , Addison-Wesley, Reading MA (1989).

M. Grötschel, L. Lovâsz, and A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization, Combinatorica 1 , (1981) 169–197.

W.K. Hale, Frequency assignment: theory and applications, Proc. of The IEEE Vol 68, No. 12, (1980) pp. 1497–1514.

W.K. Hale, New spectrum management tools, IEEE International Symposium on Electromagnetic Compatibility , Boulder, CO (1981) pp. 4753.

F. Harary, Graph Theory , Addison-Wesley Publishing Company, Reading, MA (1969).

A. Hertz, COSINE: a new graph coloring algorithm, Operations Research Letters 10 , (1991) pp. 411–415.

H. Holland, Adaptation in Natural and Artificial Systems , University of Michigan Press, Ann Arbor, MI (1975).

S. Hurley and D. H. Smith, Fixed spectrum frequency assignment using natural algorithms, Genetic Algorithms in Engineering Systems: Innovations and Applications , IEE Conference Publication No. 414, (1995).

T.R. Jensen and B. Toft, Graph Coloring Problems , John Wiley and Sons, New York, (1995).

MATH   Google Scholar  

P.K. Johri, An insight into dynamic channel assignment in cellular mobile communications systems, European Journal of Operations Research , 74 , (1994) pp. 70–77.

N. Karmarkar, An interior point approach to NP-Complete problems - part 1, Contemporary Mathematics , Vol 114, (1990) pp. 297–308.

I. Katzela and M. Naghshineh, Channel assignment schemes for cellular mobile telecommunication systems: a comprehensive survey, IEEE Personal Communications (June 1996), pp. 10–31.

D. Karger, R. Motwani and M. Sudan, Approximate graph coloring by semidefinite programming, INCOMPLETE

S. Kirkpatrick, C.D, Gelatt, Jr., and M.P. Vecchi, Optimization by simulated annealing, Science , Vol 220 , (1983) pp. 671–680.

Y. Kishi, T. Mizuike and F. Watanabe, A unified approach for frequency assignment of cellular mobile networks, Third Annual International Conference on Universal Personal Communications , San Diego , CA , (1994) pp. 563–567.

T. Kurokawa and S. Kozuka, Use of neural networks for the optimum frequency assignment problem, Electronics and Communications in Japan , Part 1, Vol, 77, No, 11, (1994).

T.A. Lanfear, Graph Theory and Radio Frequency Assignment , Tech nical Report, Allied Radio Frequency Agency NATO Headquarters, B1110, Brussels, Belgium, (1989).

D.S.P. Leung, Application of the partial backtracking technique to the frequency assignment problem, IEEE International Symposium on Electromagnetic Compatibility , Boulder, CO (1981) pp. 70–74.

D. D. Liu, Graph homomorphisms and the channel assignment problem, Ph.D. Thesis, Department of Mathematics, University of South Carolina, Colombia, SC (1991).

D.W. Matula and L.L. Beck, Smallest-last ordering and clustering and graph coloring algorithms, Journal of The ACM , Vol. 30, (1983) pp. 417–427.

B.H. Metzger, Spectrum management technique, paper presented at the 38th National ORSA Meeting , Detroit, MI, (1970).

L.C. Middlecamp, UHF taboos–history and development, IEEE Transactions on Consumer Electronics , Vol CE24, (1978) pp. 514–519.

G.L. Nemhauser and L.A. Wolsey, Integer and Combinatorial Optimization , John Wiley and Sons, Inc., (1988).

R.J. Opsut and F.S. Roberts, I-colorings, I-phasings, and I-intersection assignments for graphs, and their applications, Networks , Vol. 13 (1983) pp. 327–345.

P.M. Pardalos, F. Rendl and H. Wolkowicz, The Quadratic Assignment Problem: A Survey and Recent Developments, Quadratic Assignment and Related Problems , Panos M. Pardalos and Henry Wolkowicz (eds.) , DIMACS Series on Discrete Mathematics and Theoretical Computer Science , 16 American Mathematical Society, (1994) pp. 317–342.

J. Peemöller, A correction to Brelaz’s modification of Brown’s coloring algorithm, Communications of the ACM , Vol. 26, No. 8 , (1983) pp. 595–597.

A. Quellmalz, A. Knälmann and B. Müller, Efficient frequency assignment with simulated annealing, IEE Ninth International Conference on Antennas and Propagation , Eindhoven, The Netherlands, Vol. 2 , (1995).

A. Raychaudhuri, Intersection assignments, T-coloring, and powers of graphs, Ph.D . Thesis, Department of Mathematics, Rutgers University, New Brunswick, NJ, (1985).

A. Raychaudhuri, Further results on T-coloring and frequency assignment problems, SIAM Journal on Discrete Mathematics , Vol. 7 (1994), pp. 605–613.

F.S. Roberts, On the Compatibility between a graph and a simple order, Journal Combinatorial Theory , 11 (1971), pp 28–38.

F.S. Roberts, On the mobile radio frequency assignment problem and the traffic light phasing problem, Annals of New York Academy of Sciences Vol . 319 (1979) pp 466–483.

F.S. Roberts, From garbage to rainbows: generalizations of graph coloring and their applications, in Y. Alavi, G. Chartrand, O.R. Oellerman and A.J. Schwenk (eds.) Graph Theory , Combinatorics , and Applications , Vol . 2 ( Wiley, New York, 1991 ), pp. 1031–1052.

F.S. Roberts, T-colorings of graphs: recent results and open problems, Discrete Math . 93 , (1991) pp. 229–245.

F.S. Roberts, No-hole 2-distant colorings, Mathl. Comput. Modelling Vol. 17, No. 11 (1993) pp. 139–144.

D. Sakai, Generalized graph colorings and unit interval graphs, Ph.D. Thesis, RUTCOR, Rutgers University, New Brunswick University, NJ (1992).

D. Sakai and C. Wang, No-hole (r+1)-distant colorings, Discrete Math . 119 , (1993), pp. 175–189.

S. S. Skiena, The Algorithm Design Manual , TELOS, Springer-Verlag New York Inc., (1998).

D.H. Smith, Graph coloring and frequency assignment, ARS Combinatorica , Vol . 25C, (1988) pp. 205–212.

G.D. Smith, A. Kapsalis, V.J. Rayward-Smith, Radio link frequency assignment project, EUCLID CALMA Project Report 2.1 Genetic Algorithm Approaches to Solving the Radio Link Frequency Assignment Problem :, University of East Anglia, UK (1995).

S. Stahl, n-tuple colorings and associated graphs, J. Combinatorial Theory 20 (1976) pp. 185–203.

B.A. Tesman, T-colorings, list T-colorings, and set T-colorings of graphs, Ph.D. Thesis, Department of Mathematics, Rutgers University, New Brunswick, NJ, (1989).

B.A. Tesman, Applications of forbidden difference graphs to T- colorings, Congrussus Numerantium 74 (1990) pp. 15–24.

B. A. Tesman, Set T-colorings, Congrussus Numerantium 77 (1990) pp. 229–242.

S. Tiourine, C. Hurkins and J. K. Lenstra, An overview of algorithmic approaches to frequency assignment problems, EUCLID CALMA Project Overview Report , Delft University of Technology, The Netherlands, (1995).

D. Sakai Troxell, No-hole k-tuple (r+1)-distant colorings, Discrete Applied Math . 64 , (1996) pp. 67–85.

D. -I . Wang, The channel assignment problem and closed neighborhood containment graphs, Ph.D. Thesis, Northeastern University, Boston, MA (1985).

J.P. Warners, T. Terlaky, C. Roos and B. Jansen, A Potential Reduction Approach to The Frequency Assignment Problem , Technical Report 9598, Faculty of Technical Mathematics and Informatics, Delft University, Delft, The Netherlands, (1995).

D. Werra, Y. Gay, Chromatic scheduling and frequency assignment, Discrete Applied Math . 49 , (1994) pp. 165–174.

H.S. Wilf, Backtrack: an 0(1) expected time algorithm for the graph coloring problem, Information Processing Letters 18 (1984) pp. 119121.

A. Wisse, Mathematical model for the radio link frequency assignment problem, EUCLID CALMA Project , Delft University of Technology, The Netherlands, (1994).

J.A. Zoellner, Frequency assignment games and strategies, IEEE Transactions on Electromagnetic Compatibility ,Vol EMC-15, (1973) pp. 191196.

J.A. Zoellner and C.L. Beall, A breakthrough in spectrum conserving frequency assignment technology, IEEE Transactions on Electromagnetic Compatibility , Vol EMC-19, (1977) pp. 313–319.

Download references

Author information

Authors and affiliations.

Wright Laboratory, Eglin AFB, FL, 32542, USA

Robert A. Murphey

Center for Applied Optimization, ISE Department, University of Florida, Gainesville, FL, 32611, USA

Panos M. Pardalos

Information Sciences Research Center, AT&T Labs Research, Florham Park, NJ, 07932, USA

Mauricio G. C. Resende

You can also search for this author in PubMed   Google Scholar

Editor information

Editors and affiliations.

Department of Computer Science, University of Minnesota, USA

Ding-Zhu Du

Institute of Applied Mathematics, Academia Sinica, P. R. China

Department of Industrial and Systems Engineering, University of Florida, USA

Rights and permissions

Reprints and permissions

Copyright information

© 1999 Springer Science+Business Media Dordrecht

About this chapter

Murphey, R.A., Pardalos, P.M., Resende, M.G.C. (1999). Frequency Assignment Problems. In: Du, DZ., Pardalos, P.M. (eds) Handbook of Combinatorial Optimization. Springer, Boston, MA. https://doi.org/10.1007/978-1-4757-3023-4_6

Download citation

DOI : https://doi.org/10.1007/978-1-4757-3023-4_6

Publisher Name : Springer, Boston, MA

Print ISBN : 978-1-4419-4813-7

Online ISBN : 978-1-4757-3023-4

eBook Packages : Springer Book Archive

Share this chapter

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

• Publish with us

Policies and ethics

• Find a journal
• Track your research