ZIB-Logo

FAP web - A website about Frequency Assignment Problems

Mathematical Optimization and Scientific Information
Zuse Institute Berlin

FAP Test Problems (Benchmark instances)

At this moment information about 3 sets of benchmark instances is available at FAP web: Other instances that are available: Do you have additional information, please fill out this form.

CALMA Frequency Assignment problems

Introduction

In the context of the EUCLID (EUropean Cooperation for the Long term In Defence) CALMA (Combinatorial ALgorithms for Military Applications) project, two sets of frequency assignment problems have been made available. In the CALMA project researchers from England, France, and the Netherlands tested different combinatorial algorithms on the same set of frequency assignment problems. Eleven instances were provided by CELAR (Centre d'Electronique de l'ARmement France), whereas a second set of 14 instances was made available by the research group of Delft University of Technology. These GRAPH (Generating Radio Link Frequency Assignment Problems Heuristically) instances were randomly generated by [Van Benthem, 1995], and have the same characteristics as the CELAR instances. More documentation on the CELAR instances can be found here (thanks to Thomas Schiex).

Characteristics

The CALMA instances differ from other frequency assignment problems by their specific distance /separation constraints. Besides the minimum distance constraints, the instances also contain equality constraints, to model that two frequencies at a fixed distance have to be assigned to the corresponding vertices. The distance is the same for all constraints and every vertex is contained in exactly one equality constraint. Moreover, the domains are constructed in such a way that for every frequency there exists only one `matching' frequency. Altogether, these characteristics provide the possibility to reduce the size of the instances to half the original size whenever that may be profitable. The number of available frequencies for a vertex is 40 on average. The set of instances contains Minimum Order FAPs, Minimum Span FAPs, as well as Minimum Interference FAPs. The table below shows for every instance which objective should be taken into account as well as the number of vertices and edges in the original graph formulation, and in the reduced graph by consideration of frequency pairs. The reduced graph figures are only computed in case the objective is to minimize the interference (in this case the reduced graph is used for computations). [Aardal et al., 1999] (extended abstract published as [Aardal et al., 1996]) presented an overview of the different approaches applied in connection with the project (see also [Tiourine et al., 1995], and [Cabon et al., 1999]). At the end of this page known results for the instances are presented.
InstanceObjectiveOriginal graphReduced graph
|V||E||V||E|
CELAR 01Minimum Order9165,548
CELAR 02Minimum Order2001,235
CELAR 03Minimum Order4002,760
CELAR 04Minimum Order6803,967
CELAR 05Minimum Span4002,598
CELAR 06Minimum Interference2001,322100350
CELAR 07Minimum Interference4002,865200817
CELAR 08Minimum Interference9165,7444581,655
CELAR 09Minimum Interference6804,1033401,130
CELAR 10Minimum Interference6804,1033401,130
CELAR 11Minimum Order6804,103
GRAPH 01Minimum Order2001,134
GRAPH 02Minimum Order4002,245
GRAPH 03Minimum Span2001,134
GRAPH 04Minimum Span4002,244
GRAPH 05Minimum Interference2001,134100416
GRAPH 06Minimum Interference4002,170200843
GRAPH 07Minimum Interference4002,170200843
GRAPH 08Minimum Order6803,757
GRAPH 09Minimum Order9165,246
GRAPH 10Minimum Span6803,907
GRAPH 11Minimum Interference6803,7573401,425
GRAPH 12Minimum Interference6804,0173401,255
GRAPH 13Minimum Interference9165,2734581,877
GRAPH 14Minimum Order9164,638

Download

The problem instances can now be downloaded by clicking the following links:

Each instance is distributed in four files in a single directory.

A description of the syntax of those files is given at the CALMA page of Thomas Schiex. A copy can be found here.

Results

The tables below shows the results available for the CALMA instances. Clicking the head of columns results in the particular paper which reports the results.

Minimum Order CALMA Instances

instance lower bounds optimal value (range) upper bounds
[Aardal et al., 1996] [Aardal et al., 1996] [Aardal et al., 1996] [Aardal et al., 1996] [Tiourine et al., 1999] [Kolen et al., 1994] [Kolen et al., 1994] [Tiourine et al., 1999] [Tiourine et al., 1999] [Tiourine et al., 1999] [Bouju et al., 1995b] [Bouju et al., 1995b] [Kapsalis et al., 1995] [Warners et al., 1997] [Pasechnik, 1998] [Crisan and Mühlenbein, 1998]
clique bound coloring number generalized coloring number linear programming relaxation clique bound constraint satisfaction constraint satisfaction simulated annealing variable depth search tabu search tabu search GENET genetic algorithm potential reduction gradient descent evolutionary search
CELAR 01 12 14 16 16 14 16 16 16 16 16 16 18 16 20 16 16 -
CELAR 02 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14
CELAR 03 12 14 14 14 14 14 14 14 14 14 14 14 14 16 16 14 14
CELAR 04 - - - 46 46 46 46 46 46 46 46 46 46 46 46 46 -
CELAR 11 20 20 20 22 22 22 22 22 24 24 22 24 24 32 - 22 -
GRAPH 01 - - - 18 18 18 18 18 - - 18 18 18 20 18 18 18
GRAPH 02 - - - 14 14 14 14 14 - - 14 16 14 16 14 14 14
GRAPH 08 - - - - 16 - 16-18 - - - 20 24 22 - 18 18 -
GRAPH 09 - - - - 18 18 18 18 - - 22 22 22 28 18 18 -
GRAPH 14 - - - - 8 - 8 10 - - 10 12 - 14 10 8 -

Minimum Span CALMA Instances

instance lower bounds upper bounds
[Aardal et al., 1996] [Tiourine et al., 1999] [Kolen et al., 1994] [Tiourine et al., 1999] [Bouju et al., 1995a] [Bouju et al., 1995b] [Warners et al., 1997] [Pasechnik, 1998]
linear programming quadratic programming constraint satisfaction tabu search tabu search GENET potential reduction potential reduction
CELAR 05 792 792 792 792 792 792 792 792
GRAPH 03 - - 380 380 - - - 380
GRAPH 04 - - 394 394 - - - 394
GRAPH 10 - - 394 394 - - 394 394

Minimum Interference CALMA Instances

instance lower bounds optimal value (range) upper bounds
[Aardal et al., 1996] [Tiourine et al., 1999] [Givry et al., 1997] [Koster, 1999, Koster et al., 2002] [Koster, 1999, Koster et al., 2001] [Cooper et al., 2008] [Sanchez et al., 2009] [Allouche et al., 2010] [Kolen, 1999] [Kapsalis et al., 1995] [Tiourine et al., 1999] [Tiourine et al., 1999] [Warners et al., 1997] [Pasechnik, 1998]
linear programming quadratic programming constraint satisfaction tree decomposition integer programming constraint satisfaction constraint satisfaction / tree deco tree decomposition / parallel DP genetic algorithm genetic algorithm simulated annealing variable depth search potential reduction potential reduction
CELAR 06 5 - 3,389 3,389 2,321 3,389 3,389 3,389 3,389 3,389 3,456 3,671 3,532 4,539 4,564
CELAR 07 5 - - 300,000 180,525 - 343,592 343,592 343,592 343,592 1,670,572 567,949 344,103 - 831,926
CELAR 08 - - - 87 150 - - 262 262 262 612 276 299 - 533
CELAR 09 - 14,969 - 15,571 15,571 - 15,571 15,571 15,599 15,571 15,573 15,775 15,770
CELAR 10 - 31,204 - 31,516 31,516 - 31,516 31,516 31,517 31,516 31,516 32,460 31,517
GRAPH 05 - - - 221 221 - 221 221 293 223 - - 452
GRAPH 06 - - - 4,123 4,123 - 4,123 4,123 16,020 4,189 - - 15,047
GRAPH 07 - - - 4,324 4,324 - 4,324 4,324 5,990 4,324 - - 14,183
GRAPH 11 - - - 2,553 3,016 3,080 3,080 3,080 30,312 3,513 - - 14,692
GRAPH 12 - - - 11,827 11,827 - 11,827 11,827 15,208 11,827 - - 17,372
GRAPH 13 - - - 8,676 9,925 10,110 10,110 10,110 49,205 11,130 - - 41,784
Last modified: Jan 26, 2023 by the FAP web master