# How to achieve a "balanced" min-cost flow solution

I'm not too familiar with minimum cost flows, so please bear with me. I need to calculate the minimum cost flow for a network that looks like this:

(The numbers in parentheses next to nodes indicate supply, and the numbers on the arcs indicate the capacity and cost of that arc.) There are essentially $$\binom{4}{2} = 6$$ different solutions to this minimum cost flow. For a given solution, let $$c_F$$ (resp. $$c_G$$) denote the total cost of paths that terminate at the node $$F$$ (resp. $$G$$). For example, given this solution:

we would have $$c_F = 1+3 = 4$$ and $$c_G = 2 +4 = 6$$.

Now, out of all valid solutions, I need to choose the one that minimizes $$|c_F - c_G|$$, i.e. the one that most "balances" the costs to $$F$$ vs the costs to $$G$$. Is it possible to modify the network (e.g. by adding additional arcs/nodes) to ensure that this constraint is satisfied after solving using a minimum cost flow algorithm? If not, are there any other approaches to solving this problem?

The more general setting for this problem is for networks of the form

where $$c_i, \ell \in \mathbb{R}_{> 0}$$ and $$n \geq k$$. Thanks in advance.

• @InuyashaYagami No, I also need to minimize the cost of flow. The cost does matter if you look at the general setting. Sep 18 at 4:20
• The first priority is cost of flow. Then among all solutions with minimal cost, minimize $|c_F - c_G|$. Sep 18 at 4:23
• No, because if $n > k$ then not every $B_i$ will have a path running through it. Sep 18 at 4:27
• For every $B_{i}$, do you have an edge to every $C_{j}$? Sep 18 at 4:32
• Yes. Though I'm also interested in the case where every $B_i$ only connects to a subset of the $C_j$. Sep 18 at 4:36