Complexity of a Classical Flow Restoration Problem

Dritan Nace , Michał Pióro , Artur Tomaszewski , Mateusz Żotkiewicz


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 NPhard 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.
Author Dritan Nace - [Universite de Technologie de Compiègne]
Dritan Nace,,
, Michał Pióro (FEIT / IT)
Michał Pióro,,
- The Institute of Telecommunications
, Artur Tomaszewski (FEIT / IT)
Artur Tomaszewski,,
- The Institute of Telecommunications
, Mateusz Żotkiewicz (FEIT / IT)
Mateusz Żotkiewicz,,
- The Institute of Telecommunications
Journal seriesNetworks, ISSN 0028-3045, [1097-0037 (online)]
Issue year2013
Keywords in Englishlinear programming; equivalence of separation and optimization; multicommodity flow networks; path generation; survivable network design; NP-hardness
ASJC Classification1705 Computer Networks and Communications; 1708 Hardware and Architecture; 1710 Information Systems; 1712 Software
ProjectMixed-integer programming models for joint optimization of link capacity assignment, flow scheduling, and routing in fair multicommodity flow networks. Project leader: Pióro Michał, , Phone: +48 22 234-7383, application date 07-06-2011, start date 07-12-2011, end date 06-12-2014, IT/2012/badawczy/30, Completed
WEiTI Projects financed by NSC [Projekty finansowane przez NCN]
The Develpment of Digital Communicatios. Project leader: Lubacz Józef, , Phone: 22 234 65 31, start date 04-05-2012, planned end date 31-03-2013, end date 31-12-2013, IT/2012/statut, Completed
WEiTI Działalność statutowa
Languageen angielski
Nace Pioro Tomaszewicz Zotkiewicz Complexity of a classical flow restoration problem 2013.pdf 1,010.76 KB
Score (nominal)25
Score sourcejournalList
ScoreMinisterial score = 20.0, 17-03-2020, ArticleFromJournal
Ministerial score (2013-2016) = 25.0, 17-03-2020, ArticleFromJournal
Publication indicators WoS Citations = 6; Scopus Citations = 8; GS Citations = 13.0; Scopus SNIP (Source Normalised Impact per Paper): 2013 = 1.233; WoS Impact Factor: 2013 = 0.739 (2) - 2013=1.245 (5)
Citation count*13 (2020-09-15)
Share Share

Get link to the record

* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Are you sure?