A special condition on the Minimum Cost Flow Problem

87 Views Asked by At

I am working on the following exercise:

Consider the minimum cost flow problem with the following additional constraint: For each vertex $i \in V$ we are given an upper bound $w_i$ for the amount of flow which enters vertex $i$. How can this version be transformed to the classical minimum cost flow problem?

I would say that it should be enough to replace the capacities $u$ with $w < u$ by $u^\prime := u-w$. Does this suffice?

1

There are 1 best solutions below

0
On BEST ANSWER

Split each node $i$ into two nodes $i'$ and $i''$, with all incoming arcs to node $i$ redirected to enter node $i'$ and all outgoing arcs from node $i$ redirected to leave node $i''$. Now introduce an arc from $i'$ to $i''$ with capacity $w_i$. It remains to define $b(i')$ and $b(i'')$ in terms of $b(i)$.