The network diversion problem

The network diversion problem can be viewed as an information operations network flow application, whereby the most advantageous combinations of nodes and links are removed from a given network so as to divert the information flow over a specified set of links. The problem can be formulated as a mixed integer programming model, but for large network sizes, the solution proves to be a formidable task. A lagrangean relaxation decomposition algorithm is proposed that exploits the underlying network flow structure, enabling problems containing thousands of nodes and links to be efficiently solved.