Advanced

Fractional Routing on Pairs of Failure-disjoint Paths

Ben-Ameur, Walid; Pioro, Michal LU and Zotkiewicz, Mateusz (2014) In Discrete Applied Mathematics 164. p.47-60
Abstract
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... (More)
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. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
in
Discrete Applied Mathematics
volume
164
pages
47 - 60
publisher
Elsevier
external identifiers
  • wos:000332427400006
  • scopus:84893719261
ISSN
1872-6771
DOI
10.1016/j.dam.2011.12.019
language
English
LU publication?
yes
id
0f78be44-f7b4-4d76-af4b-4c71f4dd1688 (old id 3410295)
date added to LUP
2013-01-28 13:05:59
date last changed
2017-01-01 03:05:23
@article{0f78be44-f7b4-4d76-af4b-4c71f4dd1688,
  abstract     = {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.<br/><br>
<br/><br>
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.},
  author       = {Ben-Ameur, Walid and Pioro, Michal and Zotkiewicz, Mateusz},
  issn         = {1872-6771},
  language     = {eng},
  pages        = {47--60},
  publisher    = {Elsevier},
  series       = {Discrete Applied Mathematics},
  title        = {Fractional Routing on Pairs of Failure-disjoint Paths},
  url          = {http://dx.doi.org/10.1016/j.dam.2011.12.019},
  volume       = {164},
  year         = {2014},
}