Min-cost flow problem

Question

Consider a min cost flow problem in a directed graph $G=(V, E)$ as follows:

(*) Min $\sum {c_{ij}f_{ij}}$

s.t.: $\sum_{j\in out(i)}{f_{ij}} - \sum_{j\in in(i)}{f_{ji}} =b(i)$ for each $i\in V$

$f_{ij} \geq 0$

$in(i)$ and $out(i)$ are the set of arcs coming into node i and going out of node i, respectively. In the formulation, $f_{ij}$ is the amount of flow routing on arc $(ij)$ and $c_{ij}$ is the unit cost of routing flow on arc $(ij)$ . For each node i, b(i) is the node demand/supply.

Claim: If * is feasible and $c_{ij} \geq 0$ for all arcs $(i,j)\in E$, the optimum value is zero.

Answer 1

Your claim is wrong in general. Take all $c_{ij}=1$ and define the $b(i)$ by in-degree minus out-degree at $i$. Take as graph one in which the $b(i)$ are not all zero. Then the problem is feasible (with all $f_{ij}$ taken to be 1 giving a feasible point). For an arbitrary feasible point, not all $f_{ij}$ can vanish, so the minimum must be strictly positive.