A polynomial multicommodity flow problem with difficult path generation
(2011) 3rd International Workshop on Reliable Networks Design and Modeling (RNDM 2011) Abstract
 In the paper we consider a commonly known network design problem with demand restoration assuming stub release. No compact linear programming (LP) formulation for the problem is known, and all known noncompact LP formulations of the problem require NPhard path generation (pricing). Therefore, the problem itself is suspected to be NPhard  this, however, is not actually known. The main result of our paper reveals a special case of the basic problem for which the resulting noncompact LP formulation still has an NPhard pricing problem, the corresponding compact LP formulation is not known either, but the problem itself is polynomial. The considered special case assumes only one failing link so that all the links but one are assumed to be... (More)
 In the paper we consider a commonly known network design problem with demand restoration assuming stub release. No compact linear programming (LP) formulation for the problem is known, and all known noncompact LP formulations of the problem require NPhard path generation (pricing). Therefore, the problem itself is suspected to be NPhard  this, however, is not actually known. The main result of our paper reveals a special case of the basic problem for which the resulting noncompact LP formulation still has an NPhard pricing problem, the corresponding compact LP formulation is not known either, but the problem itself is polynomial. The considered special case assumes only one failing link so that all the links but one are assumed to be 100% reliable. The constructed case of a polynomial multicommodity flow problem with difficult path generation is of interest since no such problem is, to the best of our knowledge, widely known. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/5365564
 author
 Nace, D. ; Pioro, Michal ^{LU} ; Tomaszewski, A. and Żotkiewicz, M.
 organization
 publishing date
 2011
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 host publication
 3rd International Congress on Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT), 2011
 pages
 5 pages
 publisher
 IEEE  Institute of Electrical and Electronics Engineers Inc.
 conference name
 3rd International Workshop on Reliable Networks Design and Modeling (RNDM 2011)
 conference location
 Budapest, Hungary
 conference dates
 20111005  20111007
 external identifiers

 scopus:84856170507
 ISSN
 21570221
 ISBN
 9781457706820
 language
 English
 LU publication?
 yes
 id
 7d1ead2332da40c0a3a33cfe9305319c (old id 5365564)
 alternative location
 http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6078878
 date added to LUP
 20160401 14:51:55
 date last changed
 20201020 01:17:16
@inproceedings{7d1ead2332da40c0a3a33cfe9305319c, abstract = {In the paper we consider a commonly known network design problem with demand restoration assuming stub release. No compact linear programming (LP) formulation for the problem is known, and all known noncompact LP formulations of the problem require NPhard path generation (pricing). Therefore, the problem itself is suspected to be NPhard  this, however, is not actually known. The main result of our paper reveals a special case of the basic problem for which the resulting noncompact LP formulation still has an NPhard pricing problem, the corresponding compact LP formulation is not known either, but the problem itself is polynomial. The considered special case assumes only one failing link so that all the links but one are assumed to be 100% reliable. The constructed case of a polynomial multicommodity flow problem with difficult path generation is of interest since no such problem is, to the best of our knowledge, widely known.}, author = {Nace, D. and Pioro, Michal and Tomaszewski, A. and Żotkiewicz, M.}, booktitle = {3rd International Congress on Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT), 2011}, isbn = {9781457706820}, issn = {21570221}, language = {eng}, publisher = {IEEE  Institute of Electrical and Electronics Engineers Inc.}, title = {A polynomial multicommodity flow problem with difficult path generation}, url = {http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6078878}, year = {2011}, }