A potential reduction approach to the frequency assignment problem

被引：12

作者：

Warners, JP ^{[1
]}

Terlaky, T ^{[1
]}

Roos, C ^{[1
]}

Jansen, B ^{[1
]}

机构：

[1] CQM BV,NL-5600 AK EINDHOVEN,NETHERLANDS

来源：

DISCRETE APPLIED MATHEMATICS | 1997年 / 78卷 / 1-3期

关键词：

interior point methods; nonlinear optimization; combinatorial optimization; binary programming; frequency assignment;

D O I：

10.1016/S0166-218X(96)00139-4

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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 approximation algorithm for this problem that is inspired by Karmarkar's interior point potential reduction approach to combinatorial optimization problems. A non convex quadratic model of the problem is developed, 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 simultaneouly. Several preprocessing techniques are discussed. We report on computational experience with both real-life and randomly generated instances.

引用

页码：251 / 282

页数：32

共 22 条

[1]

AARDAL K, 1995, BRANCH AND CUT ALGOR

[2]

BLOEMEN AAF, 1992, MATH IND

[3]

DIKIN II, 1967, DOKL AKAD NAUK SSSR+, V174, P747

[4] Duality and sensitivity in nonconvex quadratic optimization over an ellipsoid [J].