Find a network flow solution which maximises the flow from a specific source to a specific sink

Question

My problem is the following and has its roots in the modeling of a gas network.

We model a gas network as a graph (E,V) with the sources being the major gas producers and the sinks being the gas consuming countries, both belonging to the V vertices set. Max constraints are set on all edges and represent the technical capacity of the network. Min constraints are set on a subset of the edges to avoid too "unrealistic" solutions. Costs are by default not used.

The problem here can be formulated as : find in the solution space of the standard network flow problem for this network the solution(s) which maximise(s) the flow from a specific source to a specific sink. For this we can either vary the edge costs or add new edge minimums in order to "push" the gas to its desired destination.

Any help would be greatly appreciated...

Answer 1

This is a variation on the multi-commodity flow problem.

Those problems are especially difficult to solve when the flows are required to be integers, i.e. the flow from one source s_d to one demand t_d cannot be 'split' into several pathes from s_d to t_d.

I assume that this is the case for your problem, i.e. you can send the gaz through several path from one source to one destination, which seems 'reasonable'.

There is an extensive literature on the topic, which mainly focus in solving either the integer version or very large instances of the problem (which arise in telecomunication networks and transportation problems); if your problem is small a simple linear solver will suffice.

The network graph is denoted (E,V) as in the question; I assume directed vertices.

I consider a set D of demands, with for each d in D a source s_d, a destination t_d and a value V_d. The values V_d are constants, except for the specific demand d0 for which you want to maximize this value. Let:

• c^{min}_e be the maximum capacity on the edge e in E
• c^{max}_e be the minimum capacity on the edge e in the subset E' of edges with such capacities

For a node v in V:

• delta_{vd} is 1 if v = t_d, -1 if v = s_d, and 0 otherwise
• E^+_v is the set of edges with head v
• E^-_v is the set of edges with tail v

I introduce, for each edge e and for each demand d, a variable x_{ed} which represents the quantity of the flow of d that goes through the edge e.

The problem can be written as a linear (continuous) model of the form:

maximize V_{d0} on x and V_{d0}

subject to:

       // flow constraints
       forall v in V, d in D:
         sum_{e in E^+_v x_{ed} - sum_{e in E^-_v} x_{ed} = V_d delta_{vd}

       // max capacity constraints
       forall e in E:
         sum_{d in D} x_{ed} <= c^{max}_e

       //  min capacity constraints
       forall e in E':
         sum_{d in D} x_{ed} >= c^{min}_e

       //  bound constraints on the variable `x`
       forall d in D, forall e in E:
         0 <= x_{ed} <= V_d