Taking into account the dynamic nature of traffic in telecommunication networks, the robust network design problem is to fix the edge capacities so that all demand vectors belonging to a polytope can be routed. While a common heuristic for this co-NP-hard problem is to compute, in polynomial time, an optimal static routing, affine routing can be used to obtain better solutions. It consists in restricting the routing to affinely depend on the demands. We show that a node-arc formulation is less conservative than an arc-path formulation. We also provide a cycle-based formulation that is equivalent to the node-arc formulation. To further reduce the solution's cost, several new formulations are obtained by relaxing flow conservation constraints and aggregating demands. As might be expected, aggregation allows us to reduce the size of formulations. A more striking result is that aggregation reduces the solution's cost.

Affine routing for robust network design

Elias, Jocelyne
2022

Abstract

Taking into account the dynamic nature of traffic in telecommunication networks, the robust network design problem is to fix the edge capacities so that all demand vectors belonging to a polytope can be routed. While a common heuristic for this co-NP-hard problem is to compute, in polynomial time, an optimal static routing, affine routing can be used to obtain better solutions. It consists in restricting the routing to affinely depend on the demands. We show that a node-arc formulation is less conservative than an arc-path formulation. We also provide a cycle-based formulation that is equivalent to the node-arc formulation. To further reduce the solution's cost, several new formulations are obtained by relaxing flow conservation constraints and aggregating demands. As might be expected, aggregation allows us to reduce the size of formulations. A more striking result is that aggregation reduces the solution's cost.
Al‐Najjar, Yacine; Ben‐Ameur, Walid; Leguay, Jérémie; Elias, Jocelyne
File in questo prodotto:
Eventuali allegati, non sono esposti

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/11585/832139
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact