Multi-Flow Optimization Model for Design of a Shared Backup Path Protected Network

Designing optimal shared backup path protected networks is a difficult and time-consuming task, and considerable research has been done to develop near optimal heuristics and algorithms that will solve the SBPP model without extensive computing power, but by definition, such methods are suboptimal. This paper introduces a slight modification to the SBPP problem that allows it to be optimally solved using conventional ILP techniques. By allowing working and backup paths to follow multiple routes, the new SBPP model eliminates the numerous 1/0 variables in the conventional model.