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 edgee in E
c^{max}_e
be the minimum capacity on the edgee
in the subsetE'
of edges with such capacities
For a node v
in V
:
delta_{vd}
is 1 ifv = t_d
, -1 ifv = s_d
, and 0 otherwiseE^+_v
is the set of edges with headv
E^-_v
is the set of edges with tailv
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