Back

G-2003-42

Lower Bounding and Tabu Search Procedures for the Frequency Assignment Problem with Polarization Constraints

, , and

BibTeX reference

The problem retained for the ROADEF'2001 international challenge was a frequency assignment problem with polarization constraints (FAPP). This NP-hard problem was proposed by the CELAR of the French Department of Defense, within the context of the CALMA project. Twenty seven competitors took part to this contest, and we present in this paper the contribution of our team that allowed us to be selected as one of the six finalists qualified for the final round of the competition.

There is typically no solution satisfying all constraints of the FAPP. For this reason, some electromagnetic compatibility constraints can be progressively relaxed, and the objective is to find a feasible solution with the lowest possible level of relaxation. We have developed a procedure that computes a lower bound on the best possible level of relaxation, as well as two tabu search algorithms for the FAPP, one for the frequency assignment and one for the polarization assignment.

, 26 pages

This cahier was revised in May 2004

Research Axis

Research application

Publication

Lower bounding and Tabu search procedures for the frequency assignment problem with polarization constraints
, , and
4OR: Quarterly Journal of the Belgian, French and Italian Operations Research Societies , 139–161, 2005 BibTeX reference