Radio Link Frequency Assignment

被引：94

作者：

Cabon B. ^{[1
]}

De Givry S. ^{[1
]}

Lobjois L. ^{[1
]}

Schiex T. ^{[2
]}

Warners J.P. ^{[3
]}

机构：

[1] Department of Computer Science, Natl. Off. Aerospatial Studs. Res., Studs. and Res. Center of Toulouse, Toulouse

[2] Dept. of Biometr. and Artif. Intell., Natl. Inst. for Agronomical Research, Toulouse

[3] Dept. of Tech. Math. and Informatics, Fac. of Info. Technology and Systems, Delft University of Technology, Delft

来源：

Constraints | 1999年 / 4卷 / 1期

关键词：

Benchmarks; Constraint satisfaction; Optimization; Radio link frequency assignment;

D O I：

10.1023/A:1009812409930

中图分类号：

学科分类号：

摘要：

The problem of radio frequency assignment is to provide communication channels from limited spectral resources whilst keeping to a minimum the interference suffered by those whishing to communicate in a given radio communication network. This problem is a combinatorial (NP-hard) optimization problem. In 1993, the CELAR (the French "Centre d'Electronique de l'Armement") built a suite of simplified versions of Radio Link Frequency Assignment Problems (RLFAP) starting from data on a real network [15]. Initially designed for assessing the performances of several Constraint Logic Programming languages, these benchmarks have been made available to the public in the framework of the European EUCLID project CALMA (Combinatorial Algorithms for Military Applications). These problems should look very attractive to the CSP community: the problem is simple to represent, all constraints are binary and involve finite domain variables. They nevertheless have some of the flavors of real problems (including large size and several optimization criteria). This paper gives essential facts about the CELAR instances and also introduces the GRAPH instances which were generated during the CALMA project.

引用

页码：79 / 89

页数：10

共 21 条

[1]

Bessiere C., Freuder E.C., Regin J.C., Using inference to reduce arc-consistency computation, IJCAI, (1995)

[2]

Bessiere C., Regin J.-C., MAC and combined heuristics: Two reasons to forsake FC (and CBJ?) on hard problems, Proc. of the Second International Conference on Principles and Practice of Constraint Programming, (1996)

[3]

Bistarelli S., Montanari U., Rossi F., Constraint solving over semirings, IJCAI, (1995)

[4]

Bloemen Ir.A.A.F., Frequency Assignment in Mobile Telecommunication Networks, (1992)

[5]

Cabon B., Problèmes D'optimisation Combinatoire : Évaluation de Méthodes de la Physique Statistique, (1996)

[6]

De Givry S., Verfaillie G., Schiex T., Bounding the Optimum of Constraint Optimization Problems, Proc. of the 3rd International Conference on Principles and Practice of Constraint Programming (CP-97), (1997)

[7]

Freuder E.C., Wallace R.J., Partial constraint satisfaction, Artificial Intelligence, 58, pp. 21-70, (1992)

[8]

Kirkpatrick S., Gelatt C.D., Vecchi M.P., Optimization by simulated annealing, Science, 220, pp. 671-680, (1983)

[9]

Kolen A., A Constraint Satisfaction Approach to the Radio Link Frequency Assignment Problem, (1994)

[10]

Kolen A., Results on Infeasible Instances of the RLFAP, (1996)

← 1 2 3 →