Combinatorial Optimization at Work: How to Find the Needle in the Haystack?

Telecommunications network design most often aims at specified technical solutions at the lowest possible cost. Discrete Mathematics can greatly help achieving this goal. The technical system is modelled in mathematical language and solved by suitable methods. It lies in the nature of those problems that they have a vast multitude of possible solutions. Singling out one with lowest cost among all of them is just like searching for a needle in a haystack. As it is a typical example for a telecommunication design problem, we will work out step-by-step the solution process of the Disjoint Routing Problem of Virtual Private Networks (VPN): a number of given demands must be routed through a given network such that their paths do not share any common nodes or links, and cause minimal cost among all possible solutions.