The frequency assignment problem involves the assignment of discrete channels (frequencies) to the transmitters of a radio network. A separation between the frequencies assigned to transmitters close to each other is required to avoid interference. Unnecessary separation causes an excess requirement for spectrum, which is a valuable resource. Consequently good assignments minimise both interference and the spectrum required. The subject of this thesis is the fixed spectrum frequency assignment problem, where the spectrum available is given and the target is to minimize the total interference of the system. Interference is modelled through binary constraints, and consequently the problem, which is treated as a combinatorial optimisation problem, can be represented by an undirected weighted graph. A summary of some of the integer programming formulations which model the problem is presented, together with a brief dimensional study of them. An efficient implementation of two well-known metaheuristic algorithms, adapted to the problem treated, is described. Some novel lower bounding techniques which, given a problem, work by combining lower bounds calculated for some of its clique-like subproblems are presented. The key idea is that it is quite easy to calculate tight lower bounds for problems represented by complete graphs (cliques). The lower bounds for clique-like subproblems are produced by two different methods, the first of which is based on the solution of a linear program, while the second is based on a closed formula. The most effective method to generate estimates for general problems is based on a linear program which is reinforced with inequalities derived from the lower bounds calculated on its clique-like subproblems. The last part of the thesis is dedicated to improvements to the lower bounding techniques, both for those working on general problems and for those developed for cliques only. Detailed computational results, obtained on a wide range of benchmarks, are reported.
| Identifer | oai:union.ndltd.org:bl.uk/oai:ethos.bl.uk:369079 |
| Date | January 2001 |
| Creators | Montemanni, Roberto |
| Publisher | University of South Wales |
| Source Sets | Ethos UK |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
| Source | https://pure.southwales.ac.uk/en/studentthesis/upper-and-lower-bounds-for-the-fixed-spectrum-frequency-assignment-problem(c8ea4370-907d-4082-a90f-b0f8854b169e).html |
Page generated in 0.002 seconds