Consistency checking within local search applied to the frequency assignment with polarization problem

Michel Vasquez; Audrey Dupont; Djamal Habet

RAIRO - Operations Research (2010)

  • Volume: 37, Issue: 4, page 311-323
  • ISSN: 0399-0559

Abstract

top
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.

How to cite

top

Vasquez, Michel, Dupont, Audrey, and Habet, Djamal. "Consistency checking within local search applied to the frequency assignment with polarization problem." RAIRO - Operations Research 37.4 (2010): 311-323. <http://eudml.org/doc/105297>.

@article{Vasquez2010,
abstract = { 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. },
author = {Vasquez, Michel, Dupont, Audrey, Habet, Djamal},
journal = {RAIRO - Operations Research},
keywords = {Filtering techniques; consistency checking; Tabu Search.; filtering techniques, consistency checking, Tabu Search},
language = {eng},
month = {3},
number = {4},
pages = {311-323},
publisher = {EDP Sciences},
title = {Consistency checking within local search applied to the frequency assignment with polarization problem},
url = {http://eudml.org/doc/105297},
volume = {37},
year = {2010},
}

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
DA - 2010/3//
PB - EDP Sciences
VL - 37
IS - 4
SP - 311
EP - 323
AB - 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.
LA - eng
KW - Filtering techniques; consistency checking; Tabu Search.; filtering techniques, consistency checking, Tabu Search
UR - http://eudml.org/doc/105297
ER -

References

top
  1. K.I. Aardal, C.A.J. Hurkens, J.K. Lenstra and S.R. Tiourine, Algorithms for Frequency Assignment Problems. CWI Quartely9 (1996) 1-9.  
  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.  
  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).  
  9. P. Hansen and N. Mladenovic, Variable Neighborhood Search. Comput. Oper. Res.24 (1997) 1097-1100 .  
  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.  
  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 .  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.