This paper considers the special case of the robust network design problem where the dominant extreme points of the demand polyhedron have a disjoint support. In this case static and dynamic routing lead to the same optimal solution, both for the splittable and the unspittable case. As a consequence, the robust network design problem with (splittable) dynamic routing is polynomially solvable, whereas it is coNP-Hard in the general case. This result applies to particular instances of the single-source Hose model.

Static and Dynamic Routing Under Disjoint Dominant Extreme Demands

FRANGIONI, ANTONIO;SCUTELLA', MARIA GRAZIA
2011-01-01

Abstract

This paper considers the special case of the robust network design problem where the dominant extreme points of the demand polyhedron have a disjoint support. In this case static and dynamic routing lead to the same optimal solution, both for the splittable and the unspittable case. As a consequence, the robust network design problem with (splittable) dynamic routing is polynomially solvable, whereas it is coNP-Hard in the general case. This result applies to particular instances of the single-source Hose model.
2011
Frangioni, Antonio; F., Pascali; Scutella', MARIA GRAZIA
File in questo prodotto:
File Dimensione Formato  
pdrelse.pdf

accesso aperto

Descrizione: Documento in Post-print
Tipologia: Documento in Post-print
Licenza: Creative commons
Dimensione 159.87 kB
Formato Adobe PDF
159.87 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11568/189508
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 3
social impact