## 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.

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 language | English |
---|---|

Publication status | Published - 2014 |

Event | 2014 INFORMS Telecommunications Conference - Lisbon, Portugal Duration: 2014 Mar 2 → 2014 Mar 4 |

### Conference

Conference | 2014 INFORMS Telecommunications Conference |
---|---|

Country/Territory | Portugal |

City | Lisbon |

Period | 2014/03/02 → 2014/03/04 |

## Subject classification (UKÄ)

- Electrical Engineering, Electronic Engineering, Information Engineering

## Keywords

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