finding optimal solution of a min network flow problem

Question

We have the following the min cost network flow problem. Notice that the arcs $(1,2), (2,3), (4,2), (3,6), (5,6)$ give a feasible basis. We easily find a feasible solution:

$$ (x_{12}, x_{23}, x_{36}, x_{42}, x_{56}) = (-6,-1,-1,-3,-1) $$

where we have assumed $b_i < 0$ is supply . When trying to find dual variables, we obtain

\begin{align*} y_1-y_2 = c_{12} = 2 \\ y_2-y_3 = c_{23} = 3 \\ y_4-y_2 = c_{42} = 5 \\ y_3-y_6= c_{36} = 3 \\ y_5-y_6 = c_{56} = 7 \\ \end{align*}

My question is, in solving this system, can we assume $y_1$ or $y_5$ to be $0$ since we can for a root node from them?

Siong Thye Goh · Accepted Answer · 2018-12-10T04:23:35.850

1

Yup, that's fine, the notion of a root node is arbitrary, just grab the node that you want it to be the root node, shake it and with the help of gravity, it becomes the root node.

To see why we can do that in terms of the algorithm. What really matters is the difference, as only the difference of the dual variables/ potential values are used in computing the optimality conditons. We have $n$ potential values and $n-1$ arcs connecting them to form the tree, fixing a value would fully determined the rest. Fixing it differently would adjust two solutions by a constant.

edited Dec 10 '18 at 04:23

answered Dec 10 '18 at 03:47

Siong Thye Goh

149,520
20
88
149

Question: Can we find another Feasible tree ? or the one I found is unique / – James Dec 10 '18 at 04:04
I could have taken path connecting node $2$ and $5$ right? – Siong Thye Goh Dec 10 '18 at 04:16
How can I see that without doing the computations? – James Dec 10 '18 at 08:07
I let node $2$, get $9$ units, then it passes the extra $1$ unit to node $5$. Then from node $5$, we pass $3$ units to node $6$. I did it by observation. To get a tree, pass $0$ units through one of the arc avoiding forming a cycle. – Siong Thye Goh Dec 10 '18 at 08:10
but the big-M method can be used to find it as well , correct ? – James Dec 10 '18 at 08:12
Sure. big $M$ can be used to find BFS and a tree corresponds to it. – Siong Thye Goh Dec 10 '18 at 08:13
So, youre saying that arcs $(2,5)$, $(5,6)$ and say $(3,6)$ is another feasible tee solution? – James Dec 10 '18 at 08:18
Let us continue this discussion in chat. – Siong Thye Goh Dec 10 '18 at 08:18

finding optimal solution of a min network flow problem

1 Answers1