Publication Details

This is an electronic version of an article originally published as: Safaei, F & Ouveysi, I, Solution of a certain class of network flow problems with cascaded demand aggregation and capacity allocation, Optimization Methods and Software, 2006, 21(4), 583–595. The journal Optimization Methods and Software can be found here through Taylor & Francis journals.


This article develops analytical models for a class of networking problems that includes two cascaded stages of demand aggregation and capacity allocation. The solutions to these problems are required in real time as the demand fluctuates rapidly. The capacity allocation problem makes a large-scale integer programming problem too complex for practical applications. Using the Lagrangian relaxation technique and a suitably developed heuristic for multiplier adjustment, the computational complexity is reduced to such a degree that a real-time implementation of the algorithm is feasible. This article also develops efficient heuristics to aggregate demand. The proposed algorithm produces a near-optimal solution in pseudo-polynomial time.



Link to publisher version (DOI)