How does the algorithm work?
The following explanation gives a glimpse of our disjoint routing algorithm. We put high emphasis on a mathematically rather involved subroutine to compute lower bounds on the optimal objective function value. To get more details, please don't hesitate to contact us directly. A powerful mathematical technique called Lagrangian Relaxation lies at the heart of our algorithm. We demonstrate this technique with a few screenshots of a simple example taken from our visualization tool. You can click on each of the thumbnails to get the originalsize images. We consider the instance given in

Figure 1: The problem. 
Figure 2: First iteration. Figure 3: Second iteration. Figure 4: The solution. 
The idea of Lagrangian Relaxation is to neglect for a
moment the fact that we need disjoint paths. It remains a
multiplesource multipledestination shortest paths problem
which can be solved efficiently. Naturally, by computing merely
shortest paths for our demands, one cannot guarantee them to be
edgedisjoint. Thus, an iterative process is used to take the
disjointness condition into account which we explain by considering
two subsequent iterations ( Suppose that we just compute these shortest paths. Usually, there
are conflicts on some edges, which means that there are some edges
used more than once. In the figures these edges are highlighted by blinking
Although this iterative procedure is easy to describe, a thorough mathematical analysis is needed to ensure both a good lower bound and fast convergence. In fact, it can be shown that in each iteration the sum of the costs of the shortest paths less the sum of all added edge costs is a lower bound on the cost of the optimum disjoint solution. In the example, after a few number of iterations a feasible
(i.e., edgedisjoint) solution, is found It is the "motor" of a BranchandBound algorithm which ultimately solves the given problem instance. It does so by dispensing with all disjointness constraints at first. It generates a series of subproblems that constitute an implicit enumeration of all feasible solutions in the form of a search tree. The branchingout in this tree, simply put, works as follows. We consider one tree node at a time and route all given demands through the network in that node. If two paths intersect in an edge, two new subproblems are generated one of which no longer allows the demand of the first path to use this edge while the other one does so with the other demand. This means, the network is successively diminished by the conflict edges found. Lower bounds are then computed for both new subproblems. 
Empirically, in most cases a feasible solution is found by the Lagrangian Relaxation subroutine. (It can be interpreted as an upper bound on the optimal solution cost). A very good lower bound is also obtained. Maintaining best possible upper and lower bounds considerably helps our BranchandBound algorithm to prune subtrees of the search tree. 
Figure 5: A plot of all iterations. 