A polynomial multicommodity flow problem with difficult path generation
Författare
Summary, in English
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.
Avdelning/ar
Publiceringsår
2011
Språk
Engelska
Publikation/Tidskrift/Serie
3rd International Congress on Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT), 2011
Länkar
Dokumenttyp
Konferensbidrag
Förlag
IEEE - Institute of Electrical and Electronics Engineers Inc.
Ämne
- Electrical Engineering, Electronic Engineering, Information Engineering
Conference name
3rd International Workshop on Reliable Networks Design and Modeling (RNDM 2011)
Conference date
2011-10-05 - 2011-10-07
Conference place
Budapest, Hungary
Status
Published
ISBN/ISSN/Övrigt
- ISSN: 2157-0221
- ISBN: 978-1-4577-0682-0