Hello Everyone,

I am modelling a network interdiction problem, where I would need to check existence of a paths between any two (source, destination) pairs. Am using a binary variable which is takes value 1 if nodes u and v are connected, and 0 otherwise. Where my objective is to maximise the number of node pairs still connected after removal of a certain number of nodes.The connections need not be direct that is path length >=1.

At the moment, I am yet to find a material on representation of paths as against arcs (direct connections). The example on telecommunications (Routing Telephone calls) is only appropriate for small graphs where is possible to list all possible paths.

Can anyone point me to how to handle in Xpress node pair connections beyond direct arc?

Thanks in anticipation?

For determining the number of connected nodes you can try a multi-commodity network flow formulation: Define K commodities, one for each source node. And for each source k define a supply capacity of commodity k equal to the number of destination nodes. For each destination node define a demand <=1 for each type of commodity k. Your objective function would be the sum of all commodities that arrive at the destination nodes.

You can also check connectivity with an all-pairs shortest path algorithm.