Cycle-based algorithms for multicommodity network flow problems with separable piecewise convex costs

Cycle-based algorithms for multicommodity network flow problems with separable piecewise convex costs

0.00 Avg rating0 Votes
Article ID: iaor200969307
Country: United States
Volume: 51
Issue: 2
Start Page Number: 133
End Page Number: 141
Publication Date: Mar 2008
Journal: Networks
Authors: , ,
Keywords: multicommodity flow
Abstract:

We present cycle-based algorithmic approaches to find local minima of a nonconvex and nonsmooth model for capacity expansion of a network supporting multicommodity flows. By exploiting complete optimality conditions for local minima, we give the convergence analysis of the negative-cost cycle canceling method. The cycle canceling method is embedded in a tabu search strategy to explore the solution space beyond the first local optimum. Reaching a local optimum, the idea is to accept a cost-increasing solution by pushing flow around a positive-cost cycle, and then to make use of the cycle cancelling method incorporating tabu search memory structures to find high quality local optima. Computational experiments on instances of the literature show that the tabu search algorithm can significantly improve feasible solutions obtained by the local optimization procedure, and it outperforms the capacity and flow assignment heuristic in terms of solution quality.

Reviews

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