Failure disjoint paths

W. Ben-Ameur, M. Żotkiewicz, Michal Pioro

Research output: Contribution to conferencePaper, not in proceedingpeer-review

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.
Original languageEnglish
Publication statusPublished - 2014
Event2014 INFORMS Telecommunications Conference - Lisbon, Portugal
Duration: 2014 Mar 22014 Mar 4

Conference

Conference2014 INFORMS Telecommunications Conference
Country/TerritoryPortugal
CityLisbon
Period2014/03/022014/03/04

Subject classification (UKÄ)

  • Electrical Engineering, Electronic Engineering, Information Engineering

Keywords

  • Shortest paths
  • disjoint paths
  • compact formulations
  • column generation
  • capacitated network design

Fingerprint

Dive into the research topics of 'Failure disjoint paths'. Together they form a unique fingerprint.

Cite this