View article

In autonomous systems of the Internet packets are routed on shortest paths to their destinations, for example according to the ECMP principle. The problem of finding a feasible traffic routing configuration realized on paths which can be generated by a system of weights assigned to IP links is NP-hard. This problem can be formulated as a mixed-integer program and attempted with a branch-and-cut algorithm if effective cuts (valid inequalities) can be derived. In this paper we present exact and approximate LP-and MIP-based methods for generating valid inequalities that separate fractional solutions of the basic problem. Besides, a family of complementary valid inequalities, generated with a shortest-path algorithm, related to combinatorial properties of feasible traffic routes is introduced to speed up the cut generation process. Results of a numerical study illustrating computational issues are discussed.