Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Failure disjoint paths

Ben-Ameur, W. ; Żotkiewicz, M. and Pioro, Michal LU (2014) 2014 INFORMS Telecommunications Conference
Abstract
Given a set of commodities and a network where some arcs can fail while others are reliable,

we first consider the problem of computing a minimum-cost pair of paths not sharing failing

links. If a reliable link belongs to both paths then its cost is counted only once. We show

that this problem can be solved in strongly polynomial time. Second, we consider a routing

problem where each commodity can be split among pairs of failure-disjoint paths. We

present a compact linear formulation of the problem. Also three non-compact formulations

solvable by column generation are introduced. All formulations are numerically compared.
Please use this url to cite or link to this publication:
author
; and
organization
publishing date
type
Contribution to conference
publication status
published
subject
keywords
Shortest paths, disjoint paths, compact formulations, column generation, capacitated network design
conference name
2014 INFORMS Telecommunications Conference
conference location
Lisbon, Portugal
conference dates
2014-03-02 - 2014-03-04
language
English
LU publication?
yes
id
6d802eb2-a75a-48b8-b735-c4f4537b0e80 (old id 5337444)
date added to LUP
2016-04-04 14:33:16
date last changed
2025-04-04 14:37:48
@misc{6d802eb2-a75a-48b8-b735-c4f4537b0e80,
  abstract     = {{Given a set of commodities and a network where some arcs can fail while others are reliable,<br/><br>
we first consider the problem of computing a minimum-cost pair of paths not sharing failing<br/><br>
links. If a reliable link belongs to both paths then its cost is counted only once. We show<br/><br>
that this problem can be solved in strongly polynomial time. Second, we consider a routing<br/><br>
problem where each commodity can be split among pairs of failure-disjoint paths. We<br/><br>
present a compact linear formulation of the problem. Also three non-compact formulations<br/><br>
solvable by column generation are introduced. All formulations are numerically compared.}},
  author       = {{Ben-Ameur, W. and Żotkiewicz, M. and Pioro, Michal}},
  keywords     = {{Shortest paths; disjoint paths; compact formulations; column generation; capacitated network design}},
  language     = {{eng}},
  title        = {{Failure disjoint paths}},
  year         = {{2014}},
}