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 条
  • [31] Frequency Fitness Assignment
    Weise, Thomas
    Wan, Mingxu
    Wang, Pu
    Tang, Ke
    Devert, Alexandre
    Yao, Xin
    IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2014, 18 (02) : 226 - 243
  • [32] Research on Frequency Assignment Problem Based on Population Replacing Genetic Ant Colony Algorithm
    Shen, Geng Biao
    Li, Fan
    Zhang, Cun Du
    Zhao, Jian Hui
    MANUFACTURING, DESIGN SCIENCE AND INFORMATION ENGINEERING, VOLS I AND II, 2015, : 129 - 134
  • [33] An alternate approach to solve two-level priority based assignment problem
    Fanrong Xie
    Anuj Sharma
    Zuoan Li
    Computational Optimization and Applications, 2022, 81 : 613 - 656
  • [34] An alternate approach to solve two-level priority based assignment problem
    Xie, Fanrong
    Sharma, Anuj
    Li, Zuoan
    COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2022, 81 (02) : 613 - 656
  • [35] Resource Assignment Problem for Fleet Management Considering Outsourcing: Modelling and a Decomposition Approach
    Monnerat, Filipe
    Dias, Joana
    Alves, Maria Joao
    COMPUTATIONAL SCIENCE AND ITS APPLICATIONS, ICCSA 2021, PT V, 2021, 12953 : 260 - 273
  • [36] The Application of Frequency Assignment Techniques in Spreading Code Assignment
    Sanusi, S. O.
    Smith, D. H.
    Jones, R. A.
    Perkins, S.
    WIRELESS PERSONAL COMMUNICATIONS, 2010, 54 (03) : 397 - 415
  • [37] The Application of Frequency Assignment Techniques in Spreading Code Assignment
    S. O. Sanusi
    D. H. Smith
    R. A. Jones
    S. Perkins
    Wireless Personal Communications, 2010, 54 : 397 - 415
  • [38] Assignment of frequency lists in frequency hopping networks
    Moon, JNJ
    Hughes, LA
    Smith, DH
    IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY, 2005, 54 (03) : 1147 - 1159
  • [39] Solving 55-Cell Benchmark Frequency Assignment Problem by Novel Nature Inspired Algorithm
    Buttar, Avtar Singh
    Goel, Ashok Kumar
    Kumar, Shakti
    2014 INTERNATIONAL CONFERENCE ON SIGNAL PROCESSING AND INTEGRATED NETWORKS (SPIN), 2014, : 407 - 411
  • [40] ACO vs EAs for Solving a Real-World Frequency Assignment Problem in GSM Networks
    Luna, Francisco
    Blum, Christian
    Alba, Enrique
    Nebro, Antonio J.
    GECCO 2007: GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE, VOL 1 AND 2, 2007, : 94 - +
12345