Core node location problem: Heuristic solvability via tabu search

We consider combinatorial problems arising in the design of Metro Core optical networks, dealing with the placement of specially equipped nodes capable of efficiently re-distributing the traffic. Two optimality criteria are considered: minimization of the maximal distance between two adjacent nodes, and minimization of the maximal path length. The paths are selected subject to the Quality of Service constraint implemented as the maximal hop length, and subject to survivability implemented as the request for having two edge disjoint paths. Integer programming formulations and a heuristic strategy based on tabu search are presented and solved either optimally using CPLEX 11.0 optimizer, or sub-optimally using a heuristic approach.