Advanced

A polynomial multicommodity flow problem with difficult path generation

Nace, D.; Pioro, Michal LU ; Tomaszewski, A. and Żotkiewicz, M. (2011) 3rd International Workshop on Reliable Networks Design and Modeling (RNDM 2011) In 3rd International Congress on Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT), 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:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
in
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)
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
2015-05-05 14:17:52
date last changed
2017-04-16 04:01:28
@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},
  pages        = {5},
  publisher    = {IEEE--Institute of Electrical and Electronics Engineers Inc.},
  title        = {A polynomial multicommodity flow problem with difficult path generation},
  year         = {2011},
}