Consistency checking within local search applied to the frequency assignment with polarization problem
RAIRO - Operations Research - Recherche Opérationnelle, Tome 37 (2003) no. 4, pp. 311-323.

We present a hybrid approach for the Frequency Assignment Problem with Polarization. This problem, viewed as Max-CSP, is treated as a sequence of decision problems, CSP like. The proposed approach combines the Arc-Consistency techniques with a performed Tabu Search heuristic. The resulting algorithm gives some high quality solutions and has proved its robustness on instances with approximately a thousand variables and nearly ten thousand constraints.

DOI : https://doi.org/10.1051/ro:2004004
Mots clés : filtering techniques, consistency checking, Tabu search
@article{RO_2003__37_4_311_0,
     author = {Vasquez, Michel and Dupont, Audrey and Habet, Djamal},
     title = {Consistency checking within local search applied to the frequency assignment with polarization problem},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {311--323},
     publisher = {EDP-Sciences},
     volume = {37},
     number = {4},
     year = {2003},
     doi = {10.1051/ro:2004004},
     zbl = {1092.90067},
     mrnumber = {2065245},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ro:2004004/}
}
Vasquez, Michel; Dupont, Audrey; Habet, Djamal. Consistency checking within local search applied to the frequency assignment with polarization problem. RAIRO - Operations Research - Recherche Opérationnelle, Tome 37 (2003) no. 4, pp. 311-323. doi : 10.1051/ro:2004004. http://archive.numdam.org/articles/10.1051/ro:2004004/

[1] K.I. Aardal, C.A.J. Hurkens, J.K. Lenstra and S.R. Tiourine, Algorithms for Frequency Assignment Problems. CWI Quartely 9 (1996) 1-9. | Zbl 0867.90129

[2] C. Bessière, Arc-consistency and Arc-consistency again. Artif. Intell. 65 (1994) 179-190.

[3] C. Bessière and J.C. Régin, Refining the Basic Consistency Propagation Algorithm, in the 17th International Joint Conference on Artificial Intelligence (IJCAI'01), Seattle-Washington, USA (2001) 309-315.

[4] R. Dorne, Étude des méthodes heuristiques pour la coloration, la T-coloration et l'affectation de fréquences. Ph.D. thesis, Université Montpellier II Sciences et Techniques du Languedoc (mai 1998).

[5] C. Fleurent and J.A. Ferland, Genetic and Hybrid Algorithms for Graph Coloring. Ann. Oper. Res. 63 (1996) 437-461. | Zbl 0851.90095

[6] P. Galinier, Étude des métaheuristiques pour la résolution du problème de satisfaction de contraintes et de coloration de graphes. Ph.D. thesis, Université Montpellier II Sciences et Techniques du Languedoc (janvier 1999).

[7] P. Galinier, S. Bisaillon, M. Gendreau and P. Soriano, Solving the Frequency Assignment Problem with Polarization by Local Search and Tabu, in The 6th Triennal Conference of the International Federation of Operational Research Societies (IFORS'02), University of Edinburgh, UK (July 2002) 8-12.

[8] F. Glover and M. Laguna, Tabu Search. Kluwer Academic Publishers (1997). | MR 1665424 | Zbl 0930.90083

[9] P. Hansen and N. Mladenovic, Variable Neighborhood Search. Comput. Oper. Res. 24 (1997) 1097-1100. | MR 1471346 | Zbl 0889.90119

[10] W.D. Harvey and M.L. Ginsberg, Limited Discrepancy Search, in Proc. of the 14th International Joint Conference on Artificial intelligence (IJCAI-95) (1995) 607-613.

[11] M. Jiang, Méthodes Approchées pour le Problème de Coloriage Généralisé Application au Problème d'Allocation de Fréquences Multiservices dans l'Aviation Civile. Ph.D. thesis, Université Versailles Saint-Quentin-en-Yvelines (novembre 1996).

[12] A.K. Mackworth, Consistency in Networks of Relations. Artif. Intell. 8 (1977) 99-118. | Zbl 0341.68061

[13] R. Mohr and T.C. Henderson, Arc and Path Consistency revisited. Artif. Intell. 28 (1986) 225-233.

[14] P Shaw, Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems, in Principle and Pratice of Constraint Programming, CP'98 (October 1998).

[15] M. Vasquez, Résolution en variables 0-1 de problèmes combinatoires de grande taille par la méthode tabou. Ph.D. thesis, Université d'Angers, UFR de Sciences (December 2000).

[16] M. Vasquez and J.K. Hao, A “Logic-Constrained” Knapsack Formulation and a Tabu Algorithm for the Daily Photograph Scheduling of an Earth Observation Satellite. Comput. Optim. Appl. 20 (2001) 137-157. | Zbl 0983.90082