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
相关论文
共 50 条
  • [21] A hybrid approach based on ant system for the Quadratic Assignment Problem
    Qi, Chengming
    PROGRESS IN INTELLIGENCE COMPUTATION AND APPLICATIONS, PROCEEDINGS, 2007, : 312 - 316
  • [22] A hybrid Hopfield network-simulated annealing approach for frequency assignment in satellite communications systems
    Salcedo-Sanz, S
    Santiago-Mozos, R
    Bousoño-Calzón, C
    IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS PART B-CYBERNETICS, 2004, 34 (02): : 1108 - 1116
  • [23] Constraint Propagation with Tabu List for Min-Span Frequency Assignment Problem
    Dib, Mohammad
    Mabed, Hakim
    Caminada, Alexandre
    MODELLING, COMPUTATION AND OPTIMIZATION IN INFORMATION SYSTEMS AND MANAGEMENT SCIENCES, PROCEEDINGS, 2008, 14 : 97 - 106
  • [24] Multi-Neighborhood simulated annealing for the minimum interference frequency assignment problem
    Ceschia, Sara
    Di Gaspero, Luca
    Rosati, Roberto Maria
    Schaerf, Andrea
    EURO JOURNAL ON COMPUTATIONAL OPTIMIZATION, 2022, 10
  • [25] A Genetic Algorithm Approach for the TV Self-Promotion Assignment Problem
    Pereira, Paulo A.
    Fontes, Fernando A. C. C.
    Fontes, Dalila B. M. M.
    NUMERICAL ANALYSIS AND APPLIED MATHEMATICS, VOLS 1 AND 2, 2009, 1168 : 1378 - +
  • [26] Channel Assignment Problem in Cellular Networks: A Reactive Tabu Search Approach
    Gozupek, Didem
    Genc, Gaye
    Ersoy, Cem
    2009 24TH INTERNATIONAL SYMPOSIUM ON COMPUTER AND INFORMATION SCIENCES, 2009, : 297 - 302
  • [27] Reducing the elastic generalized assignment problem to the standard generalized assignment problem
    Buether, M.
    JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2010, 61 (11) : 1582 - 1595
  • [28] Formulation and computationally efficient algorithms for an interference-oriented version of the frequency assignment problem
    Kotrotsos, S
    Kotsakis, G
    Demestichas, P
    Tzifa, E
    Demesticha, V
    Anagnostou, M
    WIRELESS PERSONAL COMMUNICATIONS, 2001, 18 (03) : 289 - 317
  • [29] Noisy chaotic neural networks with variable thresholds for the frequency assignment problem in satellite communications
    Wang, Lipo
    Liu, Wen
    Shi, Haixiang
    IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS PART C-APPLICATIONS AND REVIEWS, 2008, 38 (02): : 209 - 217
  • [30] Formulation and Computationally Efficient Algorithms for an Interference-Oriented Version of the Frequency Assignment Problem
    S. Kotrotsos
    G. Kotsakis
    P. Demestichas
    E. Tzifa
    V. Demesticha
    M. Anagnostou
    Wireless Personal Communications, 2001, 18 : 289 - 317
12345