Solving the Frequency Assignment Problem by Site Availability and Constraint Programming



Andréa Linhares1, Juan-Manuel Torres-Moreno2, Peter Peinl3 & Philippe Michelon4


Abstract: The efficient use of bandwidth for radio communications becomes more and more crucial when developing new information technologies and their applications. The core issues are addressed by the so-called Frequency Assignment Problems (FAP). Our work investigates static FAP, where an attempt is first made to configure a kernel of links. We study the problem based on the concepts and techniques of Constraint Programming and integrate the site availability concept. Numerical simulations conducted on scenarios provided by CELAR are very promising.

Key words: Frequency assignment, constraint programming


1 Universidade Federal do Ceará, Sobral, CE. E-mail:

2 Université d’Avignon et des Pays de Vaucluse, Avignon, France, Ecole Polytechnique de Montréal, Montréal, Canada. E-mail: 

3 University of Applied Sciences Fulda, Fulda, Germany. E-mail:

4 Ecole Polytechnique de Montr´eal, Montréal, Canada. E-mail: 


Literatura Citada

[1] K. I. Aardal, S. V. Hoesel, A. Koster, C. Mannino and A. Sassano. “Models and Solution Techniques for Frequency Assignment Problems”. 4OR, vol. 4, no. 1, pp. 261–317, 2003. 

[2] D. Fotakis, G. Pantziou, G. Pentaris and P. Spirakis. “Frequency Assignment in Mobile and Radio Networks”. DIMACS Discrete Math and Theoretical Computer Science, Networks in Distributed Computing, vol. 45, pp. 73–90, 1999. 

[3] S. Albers. “On-line Algorithms: A Survey”. Mathematical Programming, vol. Ser. B 97, pp. 3–26, May 2003. 

[4] S. Rajasekaran, K. Naik and D. Wei. “On Frequency Assignment in Cellular Networks”. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 52, pp. 293–302, 2000. 

[5] A. Dupont, A. Linhares, C. Artigues, D. Feillet, P. Michelon and M. Vasquez. “The Dynamic Frequency Assignment Problem”. European Journal of Operational Research, vol. 195, pp. 75–88, 2009. doi

[6] A. Linhares, A. Dupont, C. Artigues, D. Feillet, M. Vasquez, P. Michelon and T. Defaix. “Résolution du Problème d’Affectation de Fréquences Dynamique”. In 10ièmes JNRP NP-complets, pp. 27–42, Juin 2004.

[7] A. Linhares. “Problèmes d’Affectation de Fréquences Dynamique”. Ph.D. thesis, Université d´Avignon, Avignon, France, 2007.

[8] A. Dupont. “Etude d’une Métaheuristique Hybride pour l’Affectation de Fréquences dans les Réseaux Tactiques Évolutifs”. Ph.D. thesis, Université Montpellier II, Montpellier, France, 2005.

[9] G. Ottosson. “Integration of Constraint Prog. and Integer Prog. for Combinatorial Optimization”. Ph.D. thesis, Uppsala University, Sweden, 2000.

[10] T. Schiex. “Réseaux de Contraintes Valuées”. In 6èmes JFPLC, pp. 29–41, Marseille, France, Juin 2000.

[11] M. Schulz. “Solving Frequency Assignment Problems with Constraint Programming”. Ph.D. thesis, Institut f¨ur Mathematik der Technische Universit¨at Berlin, Berlin, Germany, 2003.

[12] P. G. J-K. Hao and M. Habib. “Méthaheuristiques pour l’optimisation combinatoire et l’affectation sous contraintes”. Revue d’Intelligence Artificielle, vol. 1, pp. 1–39, 1999.

[13] J.-M. Torres-Moreno, J. Aguilar and M. Gordon. “Finding the number minimum of errors in N-dimensional parity problem with a linear perceptron”. Neural Processing Letters, vol. 1, pp. 201–210, 2002. doi