Heuristic manipulation, tabu search and frequency assignment.

*(English)*Zbl 1173.90449Summary: Heuristic manipulation attempts to modify the search space of an optimization problem, using information provided by an underlying heuristic method. In this paper it is applied in combination with tabu search to the fixed spectrum frequency assignment problem.

The frequency assignment problem involves the assignment of discrete channels (or frequencies) to the transmitters of a radio network, such as a mobile telephone network. Frequency separation is necessary to avoid interference by other transmitters to the signal received from the wanted transmitter at the reception points. Unnecessary separation causes an excess requirement for spectrum. Good assignments minimize interference and the spectrum required. In fixed spectrum frequency assignment the frequency spectrum available is given and the target is to minimize the interference in the network.

Computational experiments confirm that the manipulation technique is able to drive the underlying tabu search algorithm towards improved solutions.

The frequency assignment problem involves the assignment of discrete channels (or frequencies) to the transmitters of a radio network, such as a mobile telephone network. Frequency separation is necessary to avoid interference by other transmitters to the signal received from the wanted transmitter at the reception points. Unnecessary separation causes an excess requirement for spectrum. Good assignments minimize interference and the spectrum required. In fixed spectrum frequency assignment the frequency spectrum available is given and the target is to minimize the interference in the network.

Computational experiments confirm that the manipulation technique is able to drive the underlying tabu search algorithm towards improved solutions.

##### MSC:

90B85 | Continuous location |

90C59 | Approximation methods and heuristics in mathematical programming |

PDF
BibTeX
XML
Cite

\textit{R. Montemanni} and \textit{D. H. Smith}, Comput. Oper. Res. 37, No. 3, 543--551 (2010; Zbl 1173.90449)

Full Text:
DOI

##### References:

[1] | Montemanni R, Smith DH, Gambardella LM. A heuristic manipulation technique for the sequential ordering problem. Computers and Operations Research 2008;35:3931-44. · Zbl 1278.90168 |

[2] | Gambardella, L.M.; Dorigo, M., An ant colony system hybridized with a new local search for the sequential ordering problem, INFORMS journal on computing, 12, 3, 237-255, (2000) · Zbl 1040.90570 |

[3] | Smith DH, Allen SM, Hurley S, Watkins WJ. Frequency assignment: methods and algorithms. In: Proceedings of the NATO RTA SET/ISET symposium on frequency assignment, sharing and conservation in systems (aerospace), Aalborg, Denmark, October 1998, NATO RTO-MP13, 1999. p. K.1-K.18. |

[4] | Murphey, R.A.; Pardalos, P.M.; Resende, M.G.C., Frequency assignment problems, (), 295-397 · Zbl 1253.90137 |

[5] | Aardal, K.I.; van Hoesel, S.P.M.; Koster, A.M.C.A.; Mannino, C.; Sassano, A., Models and solution techniques for frequency assignment problems, 4or, 1, 4, 261-317, (2003) · Zbl 1042.90049 |

[6] | Correia LM, editor. Wireless flexible personalized communications—COST 259: European co-operation in mobile radio research. New York: Wiley; 2001. COST Action 259—Final Report. |

[7] | Hurley, S.; Smith, D.H.; Thiel, S.U., Fasoft: a system for discrete channel frequency assignment, Radio science, 32, 5, 1921-1939, (1997) |

[8] | Glover, F., Heuristics for integer programming using surrogate constraints, Decision science, 8, 156-166, (1977) |

[9] | Hao, J.-K.; Dorne, R.; Galinier, P., Tabu search for frequency assignment in mobile radio networks, Journal of heuristics, 4, 47-62, (1998) · Zbl 1071.90578 |

[10] | Idoumghar, L.; Debreux, P., New modeling approach for the frequency assignment problem in broadcasting, IEEE transactions on broadcasting, 48, 4, 293-298, (2002) |

[11] | Chiarandini, M.; Stützle, T., Stochastic local search algorithms for graph set T-coloring and frequency assignment, Constraints, 12, 3, 371-403, (2007) |

[12] | Montemanni, R.; Moon, J.N.J.; Smith, D.H., An improved tabu search algorithm for the fixed spectrum frequency assignment problem, IEEE transactions on vehicular technology, 52, 4, 891-901, (2003) |

[13] | Hellebrandt M, Heller H. A new heuristic method for frequency assignment. Technical Report TD(00)003, COST259, Valencia, Spain; January 2000. |

[14] | Mannino, C.; Oriolo, G.; Ricci, F.; Chandran, S., The stable set problem and the thinness of a graph, Operations research letters, 35, 1, 1-9, (2007) · Zbl 1121.05113 |

[15] | Gendreau, M., An introduction to tabu search, (), 37-54 · Zbl 1102.90380 |

[16] | Dongarra JJ. Performance of various computers using standard linear algebra software in a fortran environment. Technical Report CS-89-85, University of Tennessee; January 2008. |

[17] | Montemanni R. Upper and lower bounds for the fixed spectrum frequency assignment problem. PhD thesis, University of Glamorgan; 2001 \(\langle\)http://www.idsia.ch/∼roberto/papers/Th2side.pdf⟩. · Zbl 1015.90069 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.