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 non-compact LP formulations of the problem require NP-hard path generation (pricing). Therefore, the problem itself is suspected to be NP-hard - this, however, is not actually known. The main result of our paper reveals a special case of the basic problem for which the resulting non-compact LP formulation still has an NP-hard 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 non-compact LP formulations of the problem require NP-hard path generation (pricing). Therefore, the problem itself is suspected to be NP-hard - this, however, is not actually known. The main result of our paper reveals a special case of the basic problem for which the resulting non-compact LP formulation still has an NP-hard 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
- 2011-10-05 - 2011-10-07
- external identifiers
-
- scopus:84856170507
- ISSN
- 2157-0221
- ISBN
- 978-1-4577-0682-0
- language
- English
- LU publication?
- yes
- id
- 7d1ead23-32da-40c0-a3a3-3cfe9305319c (old id 5365564)
- alternative location
- http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6078878
- date added to LUP
- 2016-04-01 14:51:55
- date last changed
- 2022-05-15 21:02:15
@inproceedings{7d1ead23-32da-40c0-a3a3-3cfe9305319c,
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 non-compact LP formulations of the problem require NP-hard path generation (pricing). Therefore, the problem itself is suspected to be NP-hard - this, however, is not actually known. The main result of our paper reveals a special case of the basic problem for which the resulting non-compact LP formulation still has an NP-hard 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 = {{978-1-4577-0682-0}},
issn = {{2157-0221}},
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}},
}