Open access repository

Home Open access repository

In 2014, we launched our open-access repository which offers full text access to conference proceedings from many of our events including the INC and HAISA series. These papers are free to access and distribute (subject to citing the source).

» Openaccess proceedings » Seventh International Network Conference (INC 2008)

Seventh International Network Conference (INC 2008)

Seventh International Network Conference (INC 2008)
Plymouth, UK, July 8-10, 2008
ISBN: 978-1-84102-188-1

Title: Finding Optimal Solutions to Backbone Minimisation Problems using Mixed Integer Programming
Author(s): Mike Morgan, Vic Grout
Reference: pp53-63
Keywords: Wireless mesh networks, Network backbones, Mixed Integer Programming, Heuristics
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.
Download count: 1577

How to get this paper:

Download a free PDF copy of this paperBuy this book at

PDF copy of this paper is free to download. You may distribute this copy providing you cite this page as the source.