Fractional Routing on Pairs of Failure-disjoint Paths
(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:
https://lup.lub.lu.se/record/3410295
- author
- Ben-Ameur, Walid ; Pioro, Michal LU and Zotkiewicz, Mateusz
- organization
- publishing date
- 2014
- 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
- 2016-04-01 09:53:26
- date last changed
- 2022-01-25 17:41:36
@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}},
doi = {{10.1016/j.dam.2011.12.019}},
volume = {{164}},
year = {{2014}},
}