Complexity of a classical flow restoration problem
(2013) In Networks 62(2). p.149-160- Abstract
- In this article, we revisit a classical optimization problem
occurring in designing survivable multicommodity
flow networks. The problem, referred to as FR, assumes
flow restoration that takes advantage of the so-called
stub release. As no compact linear programming (LP)
formulation of FR is known and at the same time all
known noncompact LP formulations of FR exhibit NP-hard
dual separation, the problem itself is believed to
be NP-hard, although without a proof. In this article,
we study a restriction of FR (RFR) that assumes only
elementary (cycle-free) admissible paths—an important
case virtually not considered in the literature. The... (More) - In this article, we revisit a classical optimization problem
occurring in designing survivable multicommodity
flow networks. The problem, referred to as FR, assumes
flow restoration that takes advantage of the so-called
stub release. As no compact linear programming (LP)
formulation of FR is known and at the same time all
known noncompact LP formulations of FR exhibit NP-hard
dual separation, the problem itself is believed to
be NP-hard, although without a proof. In this article,
we study a restriction of FR (RFR) that assumes only
elementary (cycle-free) admissible paths—an important
case virtually not considered in the literature. The two
problems have the same noncompact LP formulations
as they differ only in the definition of admissible paths:
all paths (also those including cycles) are allowed in FR,
while only elementary paths are allowed in RFR. Because
of that, RFR is in general computationally more complex
than FR. The purpose of this article, is three-fold.
First, the article reveals an interesting special case of
RFR—the case with only one failing link—for which a natural
noncompact LP formulation obtained by reducing
the general RFR formulation still exhibits NP-hard dual
separation, but nevertheless this special case of RFR
is polynomial. The constructed example of a polynomial
multicommodity flow problem with difficult dual separation
is of interest since, to our knowledge, no example of
this kind has been known. In this article, we also examine
a second special case of RFR, this time assuming
two failing links instead of one, which turns out to be
NP-hard. This implies that problem RFR is NP-hard
in general (more precisely, for two or more failure states).
This new result is the second contribution of the article.
Finally, we discuss the complexity of FR in the light of our
new findings, emphasizing the differences between RFR
and FR. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/3912827
- author
- Nace, Dritan ; Pioro, Michal LU ; Tomaszewski, Artur and Zotkiewicz, Mateusz
- organization
- publishing date
- 2013
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- linear programming, equivalence of separation and optimization, multicommodity flow networks, path generation, survivable network design, NP-hardness
- in
- Networks
- volume
- 62
- issue
- 2
- pages
- 149 - 160
- publisher
- John Wiley & Sons Inc.
- external identifiers
-
- wos:000322920500007
- scopus:84882455839
- ISSN
- 1097-0037
- DOI
- 10.1002/net.21508
- language
- English
- LU publication?
- yes
- id
- 3895401b-3a42-4762-8ea5-3ff170f54b2e (old id 3912827)
- date added to LUP
- 2016-04-01 11:16:12
- date last changed
- 2022-02-25 17:50:58
@article{3895401b-3a42-4762-8ea5-3ff170f54b2e,
abstract = {{In this article, we revisit a classical optimization problem<br/><br>
occurring in designing survivable multicommodity<br/><br>
flow networks. The problem, referred to as FR, assumes<br/><br>
flow restoration that takes advantage of the so-called<br/><br>
stub release. As no compact linear programming (LP)<br/><br>
formulation of FR is known and at the same time all<br/><br>
known noncompact LP formulations of FR exhibit NP-hard<br/><br>
dual separation, the problem itself is believed to<br/><br>
be NP-hard, although without a proof. In this article,<br/><br>
we study a restriction of FR (RFR) that assumes only<br/><br>
elementary (cycle-free) admissible paths—an important<br/><br>
case virtually not considered in the literature. The two<br/><br>
problems have the same noncompact LP formulations<br/><br>
as they differ only in the definition of admissible paths:<br/><br>
all paths (also those including cycles) are allowed in FR,<br/><br>
while only elementary paths are allowed in RFR. Because<br/><br>
of that, RFR is in general computationally more complex<br/><br>
than FR. The purpose of this article, is three-fold.<br/><br>
First, the article reveals an interesting special case of<br/><br>
RFR—the case with only one failing link—for which a natural<br/><br>
noncompact LP formulation obtained by reducing<br/><br>
the general RFR formulation still exhibits NP-hard dual<br/><br>
separation, but nevertheless this special case of RFR<br/><br>
is polynomial. The constructed example of a polynomial<br/><br>
multicommodity flow problem with difficult dual separation<br/><br>
is of interest since, to our knowledge, no example of<br/><br>
this kind has been known. In this article, we also examine<br/><br>
a second special case of RFR, this time assuming<br/><br>
two failing links instead of one, which turns out to be<br/><br>
NP-hard. This implies that problem RFR is NP-hard <br/><br>
in general (more precisely, for two or more failure states).<br/><br>
This new result is the second contribution of the article.<br/><br>
Finally, we discuss the complexity of FR in the light of our<br/><br>
new findings, emphasizing the differences between RFR<br/><br>
and FR.}},
author = {{Nace, Dritan and Pioro, Michal and Tomaszewski, Artur and Zotkiewicz, Mateusz}},
issn = {{1097-0037}},
keywords = {{linear programming; equivalence of separation and optimization; multicommodity flow networks; path generation; survivable network design; NP-hardness}},
language = {{eng}},
number = {{2}},
pages = {{149--160}},
publisher = {{John Wiley & Sons Inc.}},
series = {{Networks}},
title = {{Complexity of a classical flow restoration problem}},
url = {{http://dx.doi.org/10.1002/net.21508}},
doi = {{10.1002/net.21508}},
volume = {{62}},
year = {{2013}},
}