Failure disjoint paths

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