a branch-price-and-propagate approach for optimizing igp weight setting subject to unique shortest paths
An Interior Gateway Protocol (IGP) routes Internet end-to-end traffic via the shortest paths according to a set of IGP weights assigned to the network links. These weights, which can be re-set by the administrator, uniquely determine the traffic routes and thus the network performance. Assigning and provisioning the IGP weights incurring the minimum network congestion, is a common practice in Traffic Engineering. Motivated by an application, this paper considers the problem of optimizing the IGP weights so that the shortest paths are unique in the network. Despite its relevance in the telecoms sector, the problem poses considerable modelling and optimization challenges which have yet to be addressed. We develop a constraint model for the problem, and show that even small instances are too difficult for traditional optimization approaches. Our main contribution is a new hybrid optimizer that combines constraint programming and cut/column generation in order to exploit the model structure. Our optimizer succeeds in solving most of a set of realistically sized benchmarks.
column generation valid cuts internet routing constraint propagation