On design of a survivable network architecture for dynamic routing: Optimal solution strategy and an efficient heuristic

We investigate network planning and design under volatile conditions of link failures and traffic overload. Our model is a non-simultaneous multi-commodity problem, with any particular two link failure being considered as one scenario. We show that the optimal solution model is not practically solvable for real-world problems and hence an efficient heuristic is provided which is O(n⁶) faster than the optimal model and is based on synthesizing a modified maximum spanning tree using an algorithm due to Gomory and Hu. The output of this procedure is then used to solve a much smaller linear program. Simulation results indicate that the heuristic is near optimal for problems with up to 40 nodes.