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.
@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://archive.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://archive.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://archive.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, Volume 37 (2003) no. 4, pp. 311-323. doi : 10.1051/ro:2004004. http://archive.numdam.org/articles/10.1051/ro:2004004/
[1] Algorithms for Frequency Assignment Problems. CWI Quartely 9 (1996) 1-9. | Zbl
, , and ,[2] Arc-consistency and Arc-consistency again. Artif. Intell. 65 (1994) 179-190.
,[3] Refining the Basic Consistency Propagation Algorithm, in the 17th International Joint Conference on Artificial Intelligence (IJCAI'01), Seattle-Washington, USA (2001) 309-315.
and ,[4] É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] Genetic and Hybrid Algorithms for Graph Coloring. Ann. Oper. Res. 63 (1996) 437-461. | Zbl
and ,[6] É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] 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.
, , and ,[8] Tabu Search. Kluwer Academic Publishers (1997). | MR | Zbl
and ,[9] Variable Neighborhood Search. Comput. Oper. Res. 24 (1997) 1097-1100. | MR | Zbl
and ,[10] Limited Discrepancy Search, in Proc. of the 14th International Joint Conference on Artificial intelligence (IJCAI-95) (1995) 607-613.
and ,[11] 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] Consistency in Networks of Relations. Artif. Intell. 8 (1977) 99-118. | Zbl
,[13] Arc and Path Consistency revisited. Artif. Intell. 28 (1986) 225-233.
and ,[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] 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] 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
and ,Cited by Sources: