Premium
The frequency assignment problem: A solution via nonlinear programming
Author(s) -
Allen J. David,
Helgason Richard V.,
Kennington Jeffery L.
Publication year - 1987
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/1520-6750(198702)34:1<133::aid-nav3220340111>3.0.co;2-w
Subject(s) - heuristic , bounding overwatch , computer science , mathematical optimization , key (lock) , quadratic programming , interference (communication) , quadratic assignment problem , weapon target assignment problem , binary number , integer programming , frequency assignment , linear programming , software , nonlinear programming , channel (broadcasting) , nonlinear system , algorithm , optimization problem , mathematics , telecommunications , physics , quantum mechanics , computer security , arithmetic , artificial intelligence , programming language
This paper gives a mathematical programming model for the problem of assigning frequencies to nodes in a communications network. The objective is to select a frequency assignment which minimizes both cochannel and adjacent‐channel interference. In addition, a design engineer has the option to designate key links in which the avoidance of jamming due to self interference is given a higher priority. The model has a nonconvex quadratic objective function, generalized upper‐bounding constraints, and binary decision variables. We developed a special heuristic algorithm and software for this model and tested it on five test problems which were modifications of a real‐world problem. Even though most of the test problems had over 600 binary variables, we were able to obtain a near optimum in less than 12 seconds of CPU time on a CDC Cyber‐875.