Maximizing Profits of Routing in WDM Networks

Let G = (V, E) be a ring (or chain) network representing an optical wavelength division multiplexing (WDM) network with k channels, where each edge ej has an integer capacity cj. A requestsi,ti is a pair of two nodes in G. Given m requests si,ti, i = 1, 2, ..., m, each with a profit value pi, we would like to design/route a k-colorable set of paths for some (may not be all) of the m requests such that each edge ej in G is used at most cj times and the total profit of the set of designed paths is maximized. Here two paths cannot have the same color (channel) if they share some common edge(s).