A Hybrid CP-LP Method for a Shortest Path Routing Problem

Abstract:
We consider a network routing problem, where the task is to decide paths 
for known data flows in such a way that the network capacity is not 
exceeded in any part of the network. We address the case where a 
shortest path routing protocol (e.g. OSPF) is used, which constrains the 
set of paths that can be used for different flows.

We will present a CP/LP hybrid solution for this problem, where a 
CP-based approach is used for constraining the set of allowed paths, and 
an LP relaxation is used to deal with capacity constraints.