Digest of Frequency Assignment Literature

Four categories are used in the survey article ``Flavors of FAP'' to classify frequency assignment problems. To which category a frequency assignment problem belongs is determined by its objective function. Five types of objective functions are in common use: Maximum Service FAP (Max-FAP), Minimum Blocking FAP (MB-FAP), Minimum Order FAP (MO-FAP), Minimum Span FAP (MS-FAP), and Minimum Interference FAP (MI-FAP).

For each of the five categories, [Aardal et al., 2001] survey which methods have been used on what instances by whom. This digest is a regularly update version of the original compilation, published in this article. The article can be downloaded here.

Please keep us updated about your work. Send additional information and corrections to fapzib.de

Table 1: Overview literature Max-FAP and MB-FAP

source	applied techniques					instances		comments
source	Tree Search	Integer Linear Programming	Greedy	Simulated Annealing	Adhoc	CSELT	Other	comments
[Chang and Kim, 1997]					*		*	Lagrangian relaxation and subgradient optimization
[Fischetti et al., 2000]		*				*
[Jaumard et al., 1998,Jaumard et al., 2001]		*					*	Column generation
[Kazantzakis et al., 1995]		*					*
[Mannino and Sassano, 1998]	*					*		Solve and Extend
[Mathar and Mattfeldt, 1993]				*
[Rouskas et al., 1995]		*					*
[Zhang and Yum, 1991]			*

Table 2: Overview literature MO-FAP

source	applied techniques				instances		comments
source	Tree Search	Integer Linear Programming	Genetic Algorithms	Adhoc	CALMA	Other	comments
[Aardal et al., 1996]	*	*			*		Graph theoretical lower bounds
[Baybars, 1982]		*				*
[Dorne and Hao, 1995,Dorne and Hao, 1996]			*			*
[Giortzis and Turner, 1997]	*	*				*
[Hao and Dorne, 1996]			*			*
[Kolen et al., 1994]	*				*		Constraint Logic Programming
[Walser, 1996]				*		*	Constraint Programming
[Warners et al., 1997]				*	*		Potential Reduction Method

Table 3: Overview literature MS-FAP

source

applied techniques

instances

comments

Graph Theory

Integer Linear Programming

Greedy

Tabu Search

Simulated Annealing

Genetic Algorithms

Neural Networks

Adhoc

Philadelphia

CALMA

Other

[Allen et al., 1999a,Allen et al., 1999b]

*

*

*

TSP bound, subgraphs

[Avenali et al., 2000]

*

*

TSP bound,

-walks

[Beckmann and Killat, 1999a]

*

*

[Beckmann and Killat, 1999c]

*

*

Evolutionary Search

[Cozzens and Roberts, 1982,Roberts, 1991]

*

[Gamst, 1986]

*

*

[Gamst and Rave, 1982]

*

*

[Hao et al., 1998]

*

*

[Hao and Perrier, 1999]

*

*

[Hurley et al., 1997]

*

*

*

*

*

*

FASoft software

[Janssen and Kilakos, 1997,Janssen and Kilakos, 1999]

*

*

*

TSP bound

[Janssen and Wentzell, 2000]

*

*

*

Tile Covers

[Maniezzo and Carbonaro, 2000]

*

*

*

ANT Colony optimzation

[Mannino and Sassano, 1998]

*

*

Solve and Extend

[Matsui and Tokoro, 2000,Matsui and Tokoro, 2001]

*

*

[Park and Lee, 1996]

*

Kernighan-Lin heuristic

[Raychaudhuri, 1985,Raychaudhuri, 1994]

*

TSP bound

[Rushforth and Wang, 1997]

*

*

Local Search

[Sivarajan et al., 1989]

*

*

[Smith et al., 1998]

*

*

Local Search

[Smith and Palaniswami, 1997]

*

*

[Sung and Wong, 1997]

*

*

[Tcha et al., 1997]

*

*

*

[Wang and Rushforth, 1996]

*

*

Local Search

[Zoellner and Beall, 1977]

*

*

Table 4: Overview literature MI-FAP

source

applied techniques

instances

comments

Constraint Programming

Integer Linear Programming

Tree Search

Tree Decomposition

Semidefinite Programming

Greedy

Tabu Search

Simulated Annealing

Genetic Algorithms

Neural Networks

Adhoc

Philadelphia

CALMA

COST 259

Other

[Aardal et al., 1995]

*

*

[Adjakplé and Jaumard, 1997]

*

*

*

[Al-Khaled, 1998]

*

*

[Allen et al., 1987]

*

*

nonlinear programming

[Battiti et al., 1997]

*

*

penalty function optimization

[Beckmann and Killat, 1999b]

*

*

[Borndörfer et al., 1998a]

*

*

[Borndörfer et al., 1998b]

*

*

orientation model

[Bouju et al., 1995a]

*

*

[Bouju et al., 1995b]

*

*

[Box, 1978]

*

*

[Carlsson and Grindal, 1993]

*

[Castelino et al., 1996]

*

*

*

[Crisan and Mühlenbein, 1998a,Crisan and Mühlenbein, 1998b]

*

*

*

Evolutionary Search

[W. Crompton and Stephens, 1994]

*

*

[Cuppini, 1994]

*

*

[Re et al., 1996]

*

*

[Duque-Antón et al., 1993]

*

*

[Eisenblätter, 2001]

*

*

*

*

Local Search

[Funabiki and Takefuji, 1992]

*

*

[Hellebrandt and Heller, 2000]

*

*

Threshold Accepting

[Hurkens and Tiourine, 1995]

*

*

*

Quadratic Programming

Jaimes-[Jaimes-Romero et al., 1996]

*

*

[de Urries et al., 2000]

*

*

[Kapsalis et al., 1995]

*

*

[Kim et al., 1996]

*

*

Knä[Knälmann and Quellmalz, 1994,Quellmalz et al., 1995]

*

*

[Kolen, 1999]

*

*

[Koster et al., 1998]

*

*

See also [Koster, 1999]

[Koster et al., 1999]

*

*

See also [Koster, 1999]

[Koster et al., 2001]

*

*

*

See also [Koster, 1999]

[Kunz, 1991]

*

*

[Lai and Coghill, 1996]

*

*

Evolutionary Search

[Maniezzo and Montemanni, 2000]

*

*

Lower bounding techniques

[Mannino et al., 2000]

*

Local Search

[Montemanni et al., 2000]

*

*

*

[Ngo and Li, 1998]

*

*

[Pasechnik, 1998]

*

*

Interior Point Method

[Hurkens and Tiourine, 1995,Tiourine et al., 2000]

*

*

*

[Tsang and Voudouris, 1998]

*

*

Local Search

[Valenzuela et al., 1998]

*

*

*

[Verfaillie et al., 1996]

*

*

Russian Doll Search

[Zerovnik, 1997]

*

*

Do you have additional information, please send a mail to fap

zib.de

Last modified: Tue Feb 15 15:28:32 CET 2005 by the FAP web master