An efficient algorithm for routing in WDM networks

An important problem in WDM network design is to construct a logical topology and determine an optimal routing over that topology. Mixed integer linear program (MILP) formulations to generate optimal solutions for this problem are computationally intractable, even for moderate sized networks. A standard approach is to decouple the problem of logical topology design and the problem of routing on this logical topology. Heuristics for finding the logical topology exist and a straightforward linear program (LP), based on the node-arc formulation is normally used to solve the routing problem over a given logical topology. Such LP formulations become computationally infeasible for large networks. In this paper, we present a new formulation for optimally routing traffic over a given logical topology. Our formulation is based on the arc-chain representation and minimizes the congestion of the network. We have used an implicit column generation technique and exploited the special generalized upper bounding structure of our formulation to efficiently solve the problem.