This is an application from the network design and management domain. In an optical network, traffic demands between nodes are satisfied by finding colored paths from a source to a destination. The number of colors available on each link is given. If two demands are routed over the same link, the must be assigned to different colors. If there are too many demands, some demands can be rejected. The objective is to maximize the number of accepted demands, while respecting the capacity of each link. The paths used should also have short latency, i.e. their length should not be much higher than the length of the shortest path between source and destination.
This problem is well known as a difficult problem in network design, and a large number of complete or heuristic approaches have been discussed in the literature. I discuss a new, decomposition based model in my CP2009 paper. The problem is split into two phases.
In the first phase, the routing problem is solved by finding a path for as many demands as possible, while replacing the color conditions with simple capacity constraints on the links. This means that we limit the total number of demands that can be routed over a link to the number of available colors, but ignore the more detailed condition for color assignment. The solution found may therefore be too optimistic, but it provides an upper bound on the number of demands that might be accepted. The model for the first phase uses a MIP solver to find the optimal solution.
Given the paths which have been assigned to the demands, we state a graph coloring problem as a second phase of the problem.We try to find a color for each demand, enforcing that demands routed over a link must all have different colors. This can be easily expressed with finite domain variables and one alldifferent constraint for each link. If we find a solution to this problem, we have found an optimal solution to the complete problem. If we show that the graph coloring problem has no solution, we have to remove some demands from consideration, creating a simpler graph coloring problem that we can try again. Rather than removing demands at random, we use a constraint explanation routine called QuickXPlain to find a minimal set of incompatible demands. We then remove one of those demands to resolve that infeasible sub-problem. If we find a solution for the relaxed problem, we can no longer guarantee optimality, but typically solution quality will be still very high.
Experimental results showed that for typical benchmark problems from the literature, our decomposition outperforms a complete MIP approach by several orders of magnitude.
To learn more
You can find a copy of my CP2009 paper on my website at A Hybrid Constraint Model for the Routing and Wavelength Assignment Problem. The paper won the “Best Application Paper” Award at the CP 2009 conference.