  In this paper, we consider the Delay Constrained Unsplittable Shortest Path
Routing problem which arises in the field of traffic engineering for IP
networks. This problem consists, given a directed graph and a set of
commodities, to compute a set of routing paths and the associated
administrative weights such that each commodity is routed along the unique
shortest path between its origin and its destination, according to these
weights. We present a compact MILP formulation for the problem, extending the
work in (A. Bley, 2010) along with some valid inequalities to strengthen its
linear relaxation. This formulation is used as the bulding block of an
iterative approach that we develop to tackle large scale instances. We further
propose a dynamic programming algorithm based on a tree decomposition of the
graph. To the best of our knowledge, this is the first exact combinatorial
algorithm for the problem. Finally, we assess the efficiency of our approaches
through a set of experiments on state-of-the-art instances.
