A fast heuristic algorithm for the maximum concurrent k-splittable flow problem

A fast heuristic algorithm for the maximum concurrent k-splittable flow problem

0.00 Avg rating0 Votes
Article ID: iaor200973044
Country: Germany
Volume: 4
Issue: 1
Start Page Number: 37
End Page Number: 55
Publication Date: Dec 2009
Journal: Optimization Letters
Authors: ,
Keywords: heuristics
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.

Reviews

Required fields are marked *. Your email address will not be published.