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.

  • $\begingroup$ The Simplex Algorithm is a standard method to solve these questions $\endgroup$ – Empy2 Mar 18 '16 at 15:42
  • $\begingroup$ 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/…). $\endgroup$ – Majid Mar 19 '16 at 18:19

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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.