Abstract
In this thesis, we propose methods based on constraint programming (CP) for solving an optimization problem in telecommunications, the single shortest path routing problem. The problem is to find optimal values for a set of routing configuration parameters in a shortest path routing protocol, for a given network. With optimal parameters, traffic is routed through the network in a way which is optimal w.r.t. the available bandwidths of the network links. The routing parameters define a link weight for each network link, and the routing protocol makes sure that traffic between pairs of nodes in the network is sent along shortest paths w.r.t. the chosen link weight parameters. An example of such a routing protocol is the widely used Open Shortest Path First (OSPF) protocol. We consider the version of shortest path routing that requires the shortest path to be unique for every node pair.
Our CP models for this problem use two kinds of constraints. First, we propose several different constraints for enforcing the shortestpath property, known as admissibility, on the paths used in the routing. These constraints use new problemspecific propagation methods for ruling out inadmissible sets of paths. Our models also include resourcebased constraints, for modeling the bandwidth consumption on links. Here, our central resource constraint is based on a linear programming (LP) relaxation of the problem, so our method can be understood as a hybrid CPLP method.
In the last part of the thesis, we consider different methods for organizing the search process, and present experimental results from comparing different versions of our CP models.
Our CP models for this problem use two kinds of constraints. First, we propose several different constraints for enforcing the shortestpath property, known as admissibility, on the paths used in the routing. These constraints use new problemspecific propagation methods for ruling out inadmissible sets of paths. Our models also include resourcebased constraints, for modeling the bandwidth consumption on links. Here, our central resource constraint is based on a linear programming (LP) relaxation of the problem, so our method can be understood as a hybrid CPLP method.
In the last part of the thesis, we consider different methods for organizing the search process, and present experimental results from comparing different versions of our CP models.
Original language  English 

Qualification  Doctor 
Awarding Institution  
Supervisors/Advisors 

Award date  2009 Jun 12 
Print ISBNs  9789162878160 
Publication status  Published  2009 
Bibliographical note
Defence detailsDate: 20090612
Time: 13:00
Place: E:1406
External reviewer(s)
Name: Beldiceanu, Nicolas
Title: [unknown]
Affiliation: Ècole des Mines de Nantes, Frankrike

Subject classification (UKÄ)
 Computer Science