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 : 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},
     mrnumber = {2065245},
     zbl = {1092.90067},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro:2004004/}
}
TY  - JOUR
AU  - Vasquez, Michel
AU  - Dupont, Audrey
AU  - Habet, Djamal
TI  - Consistency checking within local search applied to the frequency assignment with polarization problem
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2003
SP  - 311
EP  - 323
VL  - 37
IS  - 4
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro:2004004/
DO  - 10.1051/ro:2004004
LA  - en
ID  - RO_2003__37_4_311_0
ER  - 
%0 Journal Article
%A Vasquez, Michel
%A Dupont, Audrey
%A Habet, Djamal
%T Consistency checking within local search applied to the frequency assignment with polarization problem
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2003
%P 311-323
%V 37
%N 4
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro:2004004/
%R 10.1051/ro:2004004
%G en
%F RO_2003__37_4_311_0
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://www.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

[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

[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 | Zbl

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

[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

[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

Cité par Sources :