{"id":{"repo_id":"southwales","oai_identifier":"oai:pure.atira.dk:studenttheses/c8ea4370-907d-4082-a90f-b0f8854b169e"},"canonical_url":"https://search.dev.ndltd.org/etd/southwales/oai:pure.atira.dk:studenttheses/c8ea4370-907d-4082-a90f-b0f8854b169e","repository":{"repo_id":"southwales","name":"University of South Wales","base_url":"https://pure.southwales.ac.uk/ws/oai"},"display":{"title":"Upper and lower bounds for the fixed spectrum frequency assignment problem","abstract":"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.","abstract_html":"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.<br/><br/>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. <br/><br/>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.<br/><br/>A summary of some of the integer programming formulations which model the problem is presented, together with a brief dimensional study of them. <br/><br/>An efficient implementation of two well-known metaheuristic algorithms, adapted to the problem treated, is described.<br/><br/>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.<br/><br/>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. <br/><br/>Detailed computational results, obtained on a wide range of benchmarks, are reported.","abstract_has_math":false,"creators":["Montemanni, Robert"],"institution":null,"degree_name":"Doctoral Thesis","degree_level":"Student thesis","degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2001,"date_issued":"2001-11","date_published":"2001-11","updated_at":"2026-07-24T04:38:53Z","subjects":["Wireless communication systems"],"languages":["eng"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["oai:pure.atira.dk:studenttheses/c8ea4370-907d-4082-a90f-b0f8854b169e"],"render_values":[{"text":"oai:pure.atira.dk:studenttheses/c8ea4370-907d-4082-a90f-b0f8854b169e","href":null,"code":true}]}]},"links":{"outbound_url":"https://pure.southwales.ac.uk/en/studentTheses/c8ea4370-907d-4082-a90f-b0f8854b169e","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Montemanni, Robert"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2001-11"]},{"key":"dc:date.issued","label":"Date","values":["2001-11"]},{"key":"dc:relation.isreferencedby","label":"Dc Relation Isreferencedby","values":["https://pure.southwales.ac.uk/en/studentTheses/c8ea4370-907d-4082-a90f-b0f8854b169e"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"dc:type.qualificationlevel","label":"Dc Type Qualificationlevel","values":["Student thesis"]},{"key":"dc:type.qualificationname","label":"Dc Type Qualificationname","values":["Doctoral Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Wireless communication systems"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["oai:pure.atira.dk:studenttheses/c8ea4370-907d-4082-a90f-b0f8854b169e","https://pure.southwales.ac.uk/en/studentTheses/c8ea4370-907d-4082-a90f-b0f8854b169e"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://pure.southwales.ac.uk/files/1993375/R._Montemanni_2001_2060336.pdf"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:title","label":"Title","values":["Upper and lower bounds for the fixed spectrum frequency assignment problem"]}]}],"canonical_facts":{"dc:creator":["Montemanni, Robert"],"dc:date":["2001-11"],"dc:date.issued":["2001-11"],"dc:description.abstract":["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."],"dc:identifier":["oai:pure.atira.dk:studenttheses/c8ea4370-907d-4082-a90f-b0f8854b169e","https://pure.southwales.ac.uk/en/studentTheses/c8ea4370-907d-4082-a90f-b0f8854b169e"],"dc:identifier.uri":["https://pure.southwales.ac.uk/files/1993375/R._Montemanni_2001_2060336.pdf"],"dc:language":["eng"],"dc:relation.isreferencedby":["https://pure.southwales.ac.uk/en/studentTheses/c8ea4370-907d-4082-a90f-b0f8854b169e"],"dc:subject":["Wireless communication systems"],"dc:title":["Upper and lower bounds for the fixed spectrum frequency assignment problem"],"dc:type":["Thesis"],"dc:type.qualificationlevel":["Student thesis"],"dc:type.qualificationname":["Doctoral Thesis"]},"updated_at":"2026-07-24T04:38:53Z"}