network20q

Solving the wavelength assignment problem with a minimum number of wavelengths

Over the weekend, we were presented with the problem of wavelength assignment to end-to-end lightpaths in an optical network for the internet backbone. Obviously, each lightpath must have one wavelength, and in addition, no two lightpaths that share a link can have the same wavelength, since this is a Wavelength Division Multiplexed (WDM) scheme.

Part of this had us recognize that we could represent the wavelength assignment problem as one of graph coloring using a transformed graph, where the nodes became lightpaths, and edges existed between two nodes a, b if a and b shared a link. In this way, no two neighboring lightpaths could have the same color.

A question still remains: What is the minimum number of wavelengths (i.e. colors) we can use to solve this problem?

Today in ORF 523 we investigated this problem. It is NP-hard. The most efficient and tractable way known to solve this problem is to break the graph down into its stable sets (subsets of the nodes such that no two nodes in the subset are connected), and solve the following optimization problem:

minimize(sum of color variables, where one color variable is given to each stable set)

subject to(each vertex must get assigned one color; 0 <= color variable <= 1; color variables are integers).

So, why is this problem NP-hard? At a first glance, it looks like an LP. The problem is that each of the variables must be integer - More specifically, 0 or 1. This is a decision problem – You cannot have a fraction of a color. A stable set is either assigned a unique color, or it is not.

This leads us into another branch of optimization called integer programming (IP, or MIP for mixed integer / linear programming), which constrains the feasible region of the optimization problem to all integer points within the polyhedron.

To obtain a solution to this problem, most computer codes will solve the LP-relaxation to this problem (i.e. remove the integer constraint) by applying the procedure of column generation, whereby the dual LP is taken and solved repeatedly until a feasible solution to the primal is obtained. Once the solution to the LP-relaxation is obtained, the code will apply the technique of branch and bound, where at each stage another LP is solved by restricting the branch variable to be 0 and 1, respectively.

More information on the graph coloring problem and branch and bound, refer to http://www.optimization-online.org/DB_FILE/2010/03/2568.pdf.