Template-type: ReDif-Paper 1.0
Author-Name: Aardal K.I.
Author-Name: Hipolito A.
Author-Name: Hoesel C.P.M. van
Author-Name: Jansen B.
Author-workplace-name: METEOR
Title: A branch-and-cut algorithm for the frequency assignment problem
Abstract: The frequency assignment problem (FAP) is the problem of assigning frequencies to transmission links such that no interference between signals occurs. This implies distance constraints between assigned frequencies of links. The objective is to minimize the number of used frequencies. We present an integer linear programming formulation that is closely related to the vertex packing problem. Although the size of this formulation is an order of magnitude larger than the underlying network of links, we use the integer linear programming formulation within a branch-and-cut algorithm. This algorithm employs problem specific and generic techniques such as reduction methods, primal heuristics, and branching rules to obtain optimal solutions. We report on computational experience with real-life instances. 1
Keywords: mathematical applications; 
Series: Research Memoranda
Creation-Date: 1996
Number: 007
File-URL: http://digitalarchive.maastrichtuniversity.nl/fedora/objects/guid:196b6d6f-4d2b-4ee7-a235-23f14f5e27e3/datastreams/ASSET1/content
File-Format: application/pdf
File-Size: 236052
Handle: RePEc:unm:umamet:1996007