EDS and AI seminar, 19 October 2006 from 1:15 PM to 3:00 PM, LUCAS room Mats-Petter Pettersson, AI@CS, LU A CP-LP Approach to Network Management in OSPF Routing Abstract: We consider a routing problem related to the widely used Open Shortest Path First (OSPF) protocol, which is considered a challenge within the Constraint Programming (CP) community. We address the special version of OSPF which requires unique and symmetrical paths. To solve this problem, we propose a novel hybrid approach which combines CP and Linear Programming (LP). Our approach employs a new global constraint with problem-specific filtering algorithms to efficienly remove inconsistent values from partial solutions. Moreover, this constraint employs two LP relaxations which are used to indicate infeasible partial solutions due either to network capacity constraints, or to protocol-specific routing constraints. We show the efficiency of our complete approach on backbone networks with hundreds of different demands to route.