# It would be nice if someone has some idea! (A Diophantine system associated with a network flow)

Assume that we are given a connected network flow with n nodes, $\{1, ..., n\}$, and m arcs. For each arc, say $x_{ij}$ from node i to node j, there is a maximum capacity level given as $M_{ij}$. Assume node 1 as the source node and node n as the sink node. Assume that $x_{ij}$ denotes the amount of flow from node i to node j. I am wondering if there is any algorithm to solve the following system.

1) $\sum_{j} x_{1j}=k$    (i.e., the outgoing flow of the source node is equal to k)

2) $\sum_{j} x_{jn}=k$   (i.e., the incoming flow of the sink node is equal to k)

3) $\sum_{j} x_{ij} = \sum_{l} x_{li}$ , for i=2, ..., n-1. (i.e., the outgoing flow from each node is equal to the incoming flow to that node).

4) $x_{ij} \leq M_{ij}$

Please note that I do not like to use the network characteristics to solve the system. In fact, I need an algorithm to solve the above mentioned system as a Diophantine system to find all the solutions as m-tuple vectors. I just need to have the integer system's solutions.

I appreciate you all in advance.

• The Simplex Algorithm is a standard method to solve these questions – Empy2 Mar 18 '16 at 15:42
• Thanks Michael, but I was searching for an algorithm for this case. By the way, I expressed the problem as a Diophantine system here and got some nicer answer (see math.stackexchange.com/questions/1703319/…). – Majid Mar 19 '16 at 18:19

Second way You may consider all the possible solutions according to $x_{ij} \leq M_{ij}$, and then check each solution for the flow-conversation law.