##
A potential reduction approach to the frequency assignment problem

###
J.P. Warners, T. Terlaky, C. Roos, B. Jansen

The frequency assignment problem is the problem of assigning
frequencies to transmission links such that either no interference
occurs, or the amount of interference is minimized. We present an
algorithm for this problem that is inspired by Karmarkar's interior
point potential reduction approach to combinatorial optimization
problems. We develop a nonconvex quadratic model of the problem that
is very compact as all interference constraints are incorporated in
the objective function. Moreover, optimizing this model may result in
finding multiple solutions to the problem simultaneously. Several
preprocessing techniques are discussed. We report on computational
experience with both real--life and randomly generated instances.

Report 95-98, Faculty of
Technical Mathematics and Informatics, Delft University of Technology,
Delft, 1995.

Contact : j.p.warners@twi.tudelft.nl