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.
First way You can first solve the related equations to the source and sink nodes, and then complete the solutions by going through the related equations to the other nodes.
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.