Solution of a certain class of network flow problems with cascaded demand aggregation and capacity allocation

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.