Tabu search in multi-hop optical network design

The logical topology design of a multi-hop optical network involves choosing the logical edges and simultaneously identifying a routing strategy which minimizes congestion in the network. Even small instances of this combined problem is extremely intractable due to the presence of a large number of 0--1 variables. This problem suffers from the inherent limitations unposed by classical algorithms like the branch and bound for finding integer solutions. Several heuristic algorithms have been proposed to circumvent this setback but the performance of these heuristic algorithms vary with the type of traffic and other network related constraints. In this thesis we present a tabu search based approach to solve the logical topology design problem. We compared our results with branch and bound and HLDA, a heuristic topology design algorithm.