Routing problems which include a QoS based path control play a key role in broadband communication networks. We analyze here an algorithmic procedure based on a branch and price algorithm and on the flow deviation method to solve a non-linear k-splittable flow problem. The model can support end-to-end delay bounds on each path and we compare the behaviour of the algorithm with and without these constraints. The trade-off between QoS guaranties and CPU time is clearly established and we show that minimizing the average delay on all arcs will yield solutions close to the optimal one at a significant computational saving.

@TECHREPORT{Truffot06b,
  author = {J{\'e}r{\^o}me Truffot and Christophe Duhamel and Philippe Mahey},
  title = {{k-Splittable Delay Constrained Routing Problem: A Branch and Price Approach}},
  institution = {LIMOS},
  year = {2006},
  number = {RR-06-08},
  address = {Aubi{\`e}re, France}
}