Formulations and algorithms for the Delay Constrained Routing problem

Given a telecommunication network represented by a directed graph, our problem is to route one single stream of packets on the IP network along a min-cost path with a constraint on the maximum delay that any packet may incur. From a mathematical point of view, this problem, known as Delay Constrained Routing (DCR), can be formulated as a Mixed-Integer Second-Order Cone Program (MISOCP), where one needs to simultaneously (and "optimally") compute paths and reserve resources along the paths of the network. The DCR problem presents an interesting mixture of combinatorial and continuous structures and naturally lends itself to decomposition methods. We will discuss formulations, algorithms and computational results on real/realistic network instances.