Fractional Routing on Pairs of Failure-disjoint Paths

Summary, in English

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.

• Författare: Walid Ben-Ameur; Michal Pioro; Mateusz Zotkiewicz
• Avdelning/ar: Institutionen för elektro- och informationsteknik; ELLIIT: the Linköping-Lund initiative on IT and mobile communication
• Publiceringsår: 2014
• Språk: Engelska
• Sidor: 47-60
• Publikation/Tidskrift/Serie: Discrete Applied Mathematics
• Volym: 164
• Länkar: http://dx.doi.org/10.1016/j.dam.2011.12.019
• Dokumenttyp: Artikel i tidskrift
• Förlag: Elsevier
• Ämne: Electrical Engineering, Electronic Engineering, Information Engineering
• Status: Published
• ISBN/ISSN/Övrigt: ISSN: 1872-6771