Finding Optimal Solutions to Backbone Minimisation Problems using Mixed Integer Programming
Morgan, Mike J and Grout, Vic (2008) Finding Optimal Solutions to Backbone Minimisation Problems using Mixed Integer Programming. In: UNSPECIFIED.
|
PDF
fulltext.pdf Download (191kB) | Preview |
Abstract
Attempts to evaluate heuristic algorithms are often hampered by the lack of known exact solutions with which to compare results. This is true, in particular, in the study of network backbone design - to date, a fairly undeveloped area in mathematical optimisation. This paper uses a Mixed Integer Programming (MIP) approach to find optimal solutions to the problem of backbone minimisation in mesh networks. A simple model is formulated and then adapted to reduce the number of variables and constraints. Network reliability issues are then considered and a more complex model introduced. Finally the model is solved using a commercial solver to generate test instances with which to test the accuracy of a simulated annealing (SA) heuristic. The heuristic is shown to be accurate to within a very small error margin and the strengths and weaknesses of the two approaches are discussed.
| Item Type: | Conference or Workshop Item |
|---|---|
| Additional Information: | This paper was presented at the Seventh International Network Conference (INC 2008), 8-10 July 2008, which was held in Plymouth, UK. It was published by the University of Plymouth and details of the conference are available at http://www.cscan.org/PreviousINCEvents/inc2008/ |
| Keywords: | wireless mesh networks, network backbones, mixed integer programming, heuristics |
| Divisions: | ?? GlyndwrUniversity ?? |
| Depositing User: | ULCC Admin |
| Date Deposited: | 05 Oct 2011 09:13 |
| Last Modified: | 11 Dec 2017 20:06 |
| URI: | https://wrexham.repository.guildhe.ac.uk/id/eprint/204 |
Actions (login required)
 |
Edit Item |