This thesis considers integer programming based optimization models and algorithms to solve the Spare Channel Assignment Problem for the new synchronous optical transmission networks that use a DCS for each node of the network. Given predetermined working channels between each pair of nodes of the network, the problem is to determine the spare capacity that should be added on each link to ensure rerouting of the traffic in case of a link failure using the path restoration technique. We propose various IP models which determines not only the spare capacity on each link but also the number of each link facility needed to be installed on each link to meet the aggregated requirements of working and spare channels. The objective is to minimize the total installation cost.
We propose a branch-and-cut algorithm to solve the problem. To solve the LP relaxation of the problem, a column generation routine was devised. Moreover, some valid inequalities were found and used to strengthen the formulation. Our computational results show that the algorithm can solve real practical problems to optimality within reasonable time.
