In this paper, we propose a fast heuristic algorithm for the maximum concurrent k-splittable flow problem. In such an optimization problem, one is concerned with maximizing the routable demand fraction across a capacitated network, given a set of commodities and a constant k expressing the number of paths that can be used at most to route flows for each commodity. Starting from known results on the k-splittable flow problem, we design an algorithm based on a multistart randomized scheme which exploits an adapted extension of the augmenting path algorithm to produce starting solutions for our problem, which are then enhanced by means of an iterative improvement routine. The proposed algorithm has been tested on several sets of instances, and the results of an extensive experimental analysis are provided in association with a comparison to the results obtained by a different heuristic approach and an exact algorithm based on branch and bound rules. © Springer-Verlag 2009.
A fast heuristic algorithm for the maximum concurrent k-splittable flow problem / Massimiliano, Caramia; Sgalambro, Antonino. - In: OPTIMIZATION LETTERS. - ISSN 1862-4472. - 4:1(2010), pp. 37-55. [10.1007/s11590-009-0147-4]
A fast heuristic algorithm for the maximum concurrent k-splittable flow problem
SGALAMBRO, ANTONINO
2010
Abstract
In this paper, we propose a fast heuristic algorithm for the maximum concurrent k-splittable flow problem. In such an optimization problem, one is concerned with maximizing the routable demand fraction across a capacitated network, given a set of commodities and a constant k expressing the number of paths that can be used at most to route flows for each commodity. Starting from known results on the k-splittable flow problem, we design an algorithm based on a multistart randomized scheme which exploits an adapted extension of the augmenting path algorithm to produce starting solutions for our problem, which are then enhanced by means of an iterative improvement routine. The proposed algorithm has been tested on several sets of instances, and the results of an extensive experimental analysis are provided in association with a comparison to the results obtained by a different heuristic approach and an exact algorithm based on branch and bound rules. © Springer-Verlag 2009.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.