Fractional routing using pairs of failure-disjoint paths

• Published in: Discrete Applied Mathematics 2014-02, Vol.164 (1), p.47-60
• Main Authors: Ben-Ameur, W, Pioro, M, Zotkiewicz, M
• Format: Article
• Language: English
• Subjects: Capacitated network design; Column generation; Commodities; Compact formulations; Computer networks; Computer Science; Discrete Mathematics; Disjoint paths; Mathematical analysis; Networks; Routing (telecommunications); Shortest paths; Survivability
• ISSN: 0166-218X; 1872-6771
• DOI: 10.1016/j.dam.2011.12.019

Given a set of commodities and a network where some arcs can fail while others are reliable, we consider a routing problem with respect to a survivability requirement that each commodity can be split among pairs of failure-disjoint paths. Two paths p and p′ form a pair of failure-disjoint paths if they share only reliable arcs. The same flow is sent over p and p′, but the flow sent on a common reliable arc is not doubled. We present a compact linear formulation of the problem. Also three non-compact formulations solvable by column generation are introduced. In the first formulation, the generated columns correspond to pairs of failure-disjoint paths, while in the second formulation the generated columns correspond to simple paths. The third formulation is solved by generating pairs of arc-disjoint paths. All formulations are compared numerically. On top of that we study some generalizations and some special cases of the problem of computing a shortest pair of failure-disjoint paths. One of these generalizations is equivalent to a single-commodity capacitated network design problem.