J.L. Kennington, V.S.S. Nair, and G. Spiride
Spare capacity assignment, network survivability, network protection
This study focuses on the mathematical modeling of the optimal spare capacity assignment problem for the links of a telecommunications network. Given a network topology, a point-to-point demand matrix with demand routings, and the permissible values for link capacity, we optimize the assignment of spare capacity to the links of the network in order for it to survive single link failures. The modular spare capacity allocation problem is formulated as a mixed-integer program which is computationally expensive for all but small problem instances. To be able to solve large practical problem instances, we strengthen the continuous relaxation by including additional constraints related to cuts in the network topology graph. Our solution approach is to decompose the problem into a pair of smaller problems for which optimal solutions can be obtained within a realistic time constraint. Combining the solutions for the subproblems results in a feasible solution for the original problem. We analyze the efficiency of cut-generating techniques used to derive additional constraints, and we empirically investigate the performance of the decomposition approach. The numerical results indicate that the combination of additional constraints and the decomposition algorithm improves solution times when compared to solving the original mixed-integer program. The solution time improvement using the proposed heuristics can be as high as an order of magnitude for small problem instances, while large practical problem instances can be solved in less than half the time.
Important Links:
Go Back
