The path restoration version of the spare capacity allocation problem with modularity restrictions: Models, algorithms, and an empirical analysis

This investigation presents a strategy to construct a compact mathematical model of the path-restoration version of the spare capacity allocation problem. The strategy uses a node-arc formulation and combines constraints whenever multiple working paths affected by an edge failure have identical origins or destinations. Another unique feature of this model is the inclusion of modularity restrictions corresponding to the discrete capacities of the equipment used in telecommunication networks. The new model can be solved using a classical branch-and-bound algorithm with a linear-programming relaxation. A preprocessing module is developed, which generates a set of cuts that strengthens this linear programming relaxation. The overhead associated with the cuts is offset by the improved bounds produced. A new branch-and-bound algorithm is developed that exploits the modularity restrictions. In an extensive empirical analysis, a software implementation of this algorithm was found to be substantially faster than CPLEX 6.5.3. For a test suite of 50 problems, each having 50 nodes and 200 demands from a uniform distribution with a small variance, our new software obtained solutions guaranteed to be within 4% of optimality in five minutes of CPU time on a DEC AlphaStation.