Maximizing residual capacity in connection-oriented networks (Q955490)

Summary: The following problem arises in the study of survivable connection-oriented networks. Given a demand matrix to be routed between nodes, we want to route all demands, so that the residual capacity given by the difference between link capacity and link flow is maximized. Each demand can use only one path. Therefore, the flow is modeled as nonbifurcated multicommodity flow. We call the considered problem nonbifurcated congestion (NBC) problem. Solving NBC problem enables robust restoration of failed connections in a case of network failure. We propose a new heuristic algorithm for NBC problem and compare its performance with existing algorithms.