k‐Splittable delay constrained routing problem: A branch‐and‐price approach
Jérôme Truffot, Christophe Didier Duhamel, Philippe Mahey · Networks · 2009
Abstract 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 branch‐and‐price algorithm and on the flow deviation method to solve a nonlinear k‐splittable flow problem. The model can support end‐to‐end delay bounds on each path and we compare the behavior of the algorithm with and without these constraints. The trade‐off between QoS guarantees 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. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010