I am trying to solve a very simple minimum cost flow problem using optimization software. However, the software keeps on complaining about the problem being infeasible, which means I have most certainly not expressed the model/constraints correctly. The network is illustrated below:
- Supply nodes: 0 and 1 (75 units for each node)
- Demand nodes: 4 (50 units),5 (60 units), 6 (40 units)
- Costs in red along the arcs
- Node 3 has a max capacity of 50 units
I tried to solve the problem by defining the following equations:
Minimize the objective function: $5 x_{02}+8x_{03}+7x_{12}+4x_{13}+x_{24}+5x_{25}+8x_{26}+3x_{34}+4x_{35}+4x_{36}$
I have also defined the following constraints:
- $x_{02}+x_{03} = 75$
- $x_{12}+x_{13} = 75$
- $x_{24}+x_{34} = 50$
- $x_{25}+x_{35} = 60$
- $x_{26}+x_{36} = 40$
At the transshipment nodes 2 and 3:
- $x_{02}+x_{12}-x_{24}-x_{25}-x_{26} = 0$ (at node 2)
- $x_{03}+x_{13}-x_{34}-x_{35}-x_{36} = 0$ (at node 3)
Maximum capacity constraints at node 3:
- $x_{03} \leq 50$
- $x_{13} \leq 50$
- $x_{34} \leq 50$
- $x_{35} \leq 50$
- $x_{36} \leq 50$
Am I missing any other constraints? Are any of the above constraints expressed in a wrong way?
Thanks for your help!
Node capacity of 50 means the sum of incoming flows (which is equal to the sum of outgoing flows) at that node is at most 50. This is a tighter constraint than the five $\le$ constraints that you specified.
An optimal solution, with objective value 1250, is \begin{matrix} i &j &x_{i,j} \\ \hline 0 &2 &75 \\ 0 &3 &0 \\ 1 &2 &25 \\ 1 &3 &50 \\ 2 &4 &50 \\ 2 &5 &50 \\ 2 &6 &0 \\ 3 &4 &0 \\ 3 &5 &10 \\ 3 &6 &40 \\ \end{matrix}