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