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.
Disciplines
Computer and Systems Architecture | Digital Communications and Networking | Hardware Systems | Systems and Communications
Recommended Citation
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
Digital Commons Citation
Morgan, Mike J. and Grout, Vic, "Finding Optimal Solutions to Backbone Minimisation Problems using Mixed Integer Programming" (2008). Computing. Paper 43.
http://epubs.glyndwr.ac.uk/cair/43
Included in
Computer and Systems Architecture Commons, Digital Communications and Networking Commons, Hardware Systems Commons, Systems and Communications Commons
Comments
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