3
$\begingroup$

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:

enter image description here

(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:

enter image description here

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

enter image description here

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.