We consider a Network Design problem where edges have to be activated at minimum cost while ensuring that the resulting graph contains at least k disjoint paths linking a given set of origin-destination pairs. In addition, those paths are constrained in terms of maximum number of intermediate nodes. We consider alternative Integer Programming formulations for the problem and computationally evaluate them on a large benchmark of instances having different features. Finally, we extend our analysis to the case in which the paths must be vertex disjoint. (c) 2024 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.
Gudapati, N.V.C., Malaguti, E., Monaci, M., Paronuzzi, P. (2025). A computational study on Integer Programming formulations for Hop-constrained survivable network design. DISCRETE APPLIED MATHEMATICS, 362, 71-81 [10.1016/j.dam.2024.11.021].
A computational study on Integer Programming formulations for Hop-constrained survivable network design
Gudapati N. V. C.;Paronuzzi P.
2025
Abstract
We consider a Network Design problem where edges have to be activated at minimum cost while ensuring that the resulting graph contains at least k disjoint paths linking a given set of origin-destination pairs. In addition, those paths are constrained in terms of maximum number of intermediate nodes. We consider alternative Integer Programming formulations for the problem and computationally evaluate them on a large benchmark of instances having different features. Finally, we extend our analysis to the case in which the paths must be vertex disjoint. (c) 2024 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
