Fractional Routing on Pairs of Failuredisjoint Paths
(2014) In Discrete Applied Mathematics 164. p.4760 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 failuredisjoint paths. Two paths p and p′ form a pair of failuredisjoint 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 noncompact formulations solvable by column generation are introduced. In the first formulation, the generated columns correspond to pairs of failuredisjoint 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 failuredisjoint paths. Two paths p and p′ form a pair of failuredisjoint 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 noncompact formulations solvable by column generation are introduced. In the first formulation, the generated columns correspond to pairs of failuredisjoint paths, while in the second formulation the generated columns correspond to simple paths. The third formulation is solved by generating pairs of arcdisjoint 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 failuredisjoint paths. One of these generalizations is equivalent to a singlecommodity capacitated network design problem. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/3410295
 author
 BenAmeur, 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
 18726771
 DOI
 10.1016/j.dam.2011.12.019
 language
 English
 LU publication?
 yes
 id
 0f78be44f7b44d76af4b4c71f4dd1688 (old id 3410295)
 date added to LUP
 20130128 13:05:59
 date last changed
 20170101 03:05:23
@article{0f78be44f7b44d76af4b4c71f4dd1688, 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 failuredisjoint paths. Two paths p and p′ form a pair of failuredisjoint 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 noncompact formulations solvable by column generation are introduced. In the first formulation, the generated columns correspond to pairs of failuredisjoint paths, while in the second formulation the generated columns correspond to simple paths. The third formulation is solved by generating pairs of arcdisjoint 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 failuredisjoint paths. One of these generalizations is equivalent to a singlecommodity capacitated network design problem.}, author = {BenAmeur, Walid and Pioro, Michal and Zotkiewicz, Mateusz}, issn = {18726771}, language = {eng}, pages = {4760}, publisher = {Elsevier}, series = {Discrete Applied Mathematics}, title = {Fractional Routing on Pairs of Failuredisjoint Paths}, url = {http://dx.doi.org/10.1016/j.dam.2011.12.019}, volume = {164}, year = {2014}, }