Friday, 10:30 - 10:55 h, Room: H 3002


Michal Pioro
On a survivable network design problem with one or two failing links and elementary path-flows

Coauthors: Dritan Nace, Artur Tomaszewski, Mateusz Zotkiewicz


A well known problem in survivable network design consists in minimizing the cost of links under a single link failure scenario (any link can fail but only one at a time) assuming flow restoration. The problem, denoted by FR, assumes bifurcated primary and restoration flows, and stub release (the capacity of links released by failing flows is used for restoration). FR can be expressed as a linear program but only in a non-compact formulation with NP-hard separation. Because of that, FR is regarded as NP-hard itself although this has not been proved.
The paper considers a version of FR when only one predefined link or only two predefined links can fail. We assume that the primary paths cannot contain loops - an assumption commonly neglected. We show that the case with one failing link is polynomial while the case with two failing links is NP-hard. This is a new result that sheds light on FR also for the single link failure scenario. As a byproduct of the one-failing link case, we obtain an example of a non-compact LP formulation with NP-hard separation which actually describes a polynomial problem. Such an example has not been commonly known to the network design community before.


Talk 1 of the invited session Fri.1.H 3002
"Optimization modeling of communication networks" [...]
Cluster 23
"Telecommunications & networks" [...]


  cash loans . On the global pharmaceutical market this medicine was issued in 2003 by two companies - Eli Lilly and ICOS. Initially, permission to sell Cialis was obtained in Europe, Australia, New Zealand.