Failure disjoint paths

Summary, in English

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.

• Author: W. Ben-Ameur; M. Żotkiewicz; Michal Pioro
• Department/s: Department of Electrical and Information Technology; ELLIIT: the Linköping-Lund initiative on IT and mobile communication
• Publishing year: 2014
• Language: English
• Document type: Conference paper
• Topic: Electrical Engineering, Electronic Engineering, Information Engineering
• Keywords: Shortest paths; disjoint paths; compact formulations; column generation; capacitated network design
• Conference name: 2014 INFORMS Telecommunications Conference
• Conference date: 2014-03-02 - 2014-03-04
• Conference place: Lisbon, Portugal
• Status: Published