  


Complexity of a classical flow restoration problem
Dritan Nace(naceutc.fr) Abstract: In the paper we revisit a classical optimization problem in designing survivable multicommodity flow networks. The problem, referred to as FR, assumes flow restoration that takes advantage of the socalled 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 commonly believed to be NPhard, although without a proof. In the paper we study a restriction of FR (called RFR) that assumes only elementary (cyclefree) 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 paper is threefold. First, the paper 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 NPhard 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 the paper we also examine a second special case of RFR, this time assuming two failing links instead of one, which turns out to be NPhard. This implies that problem RFR is NPhard in general (more precisely, for two or more failure states). This new result is the second contribution of the paper. Finally, we discuss the complexity of FR in the light of the original results of the paper, emphasizing the differences between RFR and FR. Keywords: linear programming, equivalence of separation and optimization, multicommodity flow networks, path generation, survivable network design, NPhardness Category 1: Applications  OR and Management Sciences (Telecommunications ) Category 2: Linear, Cone and Semidefinite Programming (Linear Programming ) Citation: unpublished Download: [PDF] Entry Submitted: 02/14/2013 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  