Frequency assignment for cellular mobile systems using constraint satisfaction techniques

Makoto Yokoo, Katsutoshi Hirayama

Research output: Contribution to journalConference articlepeer-review

8 Citations (Scopus)


This paper presents a new algorithm for solving frequency assignment problems in cellular mobile systems using constraint satisfaction techniques. The characteristics of this algorithm are as follows: 1) instead of representing each call in a cell (a unit area in providing communication services) as a variable, we represent a cell (which has multiple calls) as a variable that has a very large domain, and determine a variable value step by step, 2) a powerful cell-ordering heuristic is introduced, 3) a branch-and-bound search that incorporates forward-checking is performed, and 4) the limited discrepancy search is introduced to improve the chance of finding a solution in a limited amount of search. Experimental evaluations using standard benchmark problems show that this algorithm can find optimal or semi-optimal solutions for these problems, and most of the obtained solutions are better than or equivalent to those of existing methods using simulated annealing, tabu search, or neural networks. These results show that state-of-the-art constraint satisfaction/optimization techniques are capable of solving realistic application problems when equipped with an appropriate problem representation and heuristics.

Original languageEnglish
Pages (from-to)888-894
Number of pages7
JournalIEEE Vehicular Technology Conference
Publication statusPublished - 2000
Externally publishedYes
EventVTC2000: 51st Vehicular Technology Conference 'Shaping History Through Mobile Technologies' - Tokyo, Jpn
Duration: May 15 2000May 18 2000

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Electrical and Electronic Engineering
  • Applied Mathematics


Dive into the research topics of 'Frequency assignment for cellular mobile systems using constraint satisfaction techniques'. Together they form a unique fingerprint.

Cite this