Weighted matching in sink source graph

Question

I have three lists of nodes. sources, sinks, and pipes. there is a directed weighted graph from sources to pipes to sinks. Sources are only connected to pipes and pipes only to sinks. But sources are not directly connected to sinks. Pipes are zero-sum, meaning that the sum of the weights that come to each pipe from sources is equal to the sum of the edges that go from that pipe to sinks.

I would like to add the minimum number of edges to this graph from sinks back to sources so that sinks and sources also become zero-sum. I know this problem is np-complete I'm interested to see if there is any good polynomial approximation to this problem that would work in real life.

In simpler words: I have a list of sinks and sources. Each sink has a negative number and each source has a positive number so that the sum of all the numbers in the nodes of the graph are zero(no edges so far). I would like to add the minimum number of edges to this graph so that the sum of the weights of the edges going out/in to each node becomes equal to the number on that node.

Example:

Given:

a0: 3
a1: 1
a2: 5
b0: -2
b1: -5
b2: -2

We get to:

a0-b0: 2
a0-b2: 1
a1-b2: 1
a2-b1: 5

Check of correctness:

a0: 3 = 2+1
a1: 1 = 1
a2: 5 = 5
b0: -2 = -2
b1: -5 = -5
b2: -2 = -1 + -1

Answer 1

This gives a sub-optimum solution with less than n-1 edges.

from numpy.random import randint
from collections import defaultdict
import copy


def create_sample(source_count=5000, sink_count=200):
    diff = -1
    while diff < 0:
        sinks = [["b" + str(i), randint(source_count)] for i in range(sink_count)]
        sources = [["a" + str(i), randint(sink_count)] for i in range(source_count)]
        sink_sum = sum([x[1] for x in sinks])
        source_sum = sum([x[1] for x in sources])
        diff = sink_sum - source_sum
    avg_refill = diff // source_count + 1
    weights_match = False
    while not weights_match:
        for i in range(source_count):
            if not diff:
                break
            rnd = randint(avg_refill * 2.5) if diff > 10 * (avg_refill) else diff
            diff -= rnd
            sources[i][1] += rnd
        weights_match = sum([x[1] for x in sources]) == sum([x[1] for x in sinks])
    return sources, sinks


def solve(sources, sinks):
    src = sorted(copy.deepcopy(sources), key=lambda x: x[1])
    snk = sorted(copy.deepcopy(sinks), key=lambda x: x[1])
    res = []
    while snk:
        if src[0][1] > snk[0][1]:
            edge = (src[0][0], *snk[0])
            src[0][1] -= snk[0][1]
            del snk[0]
        elif src[0][1] < snk[0][1]:
            edge = (src[0][0], snk[0][0], src[0][1])
            snk[0][1] -= src[0][1]
            del src[0]
        else:
            edge = (src[0][0], *snk[0])
            del src[0], snk[0]
        res += [edge]
    return res


def test(sources, sinks):
    res = solve(sources, sinks)
    d_sources = defaultdict(int)
    d_sinks = defaultdict(int)
    w_sources = defaultdict(int)
    w_sinks = defaultdict(int)
    for a, b, c in res:
        d_sources[a] += 1
        d_sinks[b] += 1
        w_sources[a] += c
        w_sinks[b] += c
    print("source " + ("is" if dict(sources) == w_sources else "isn't") + " source")
    print("sink " + ("is" if dict(sinks) == w_sinks else "isn't") + " sink")
    print(
        f"source:\n \tdeg_sum = {sum(d_sources.values())}\n\tmax_deg = {max(d_sources.values())}"
    )
    print(
        f"sink:\n \tdeg_sum = {sum(d_sinks.values())}\n\tmax_deg = {max(d_sinks.values())}"
    )

Here is a sample run:

In [1]: %run solver.py
In [2]: test(*create_sample())
source is source
sink is sink
source:
        deg_sum = 5196
        max_deg = 3
sink:
        deg_sum = 5196
        max_deg = 56

Here is an illustration of how it works:

sources: 4,5,3,2
sinks: 2,7,2,2,1

sorted:
        55555|44|44|33|32|2
        77777|77|22|22|22|1
So we have 6 edges.

Here is a comparison between sorted and unsorted solution with this algorithm:

---------------------------------------------
|                (1000,1000)                |
---------------------------------------------
| criteria          | sorted | random order |
| source degree sum | 1991   | 1999         |
| source max degree | 3      | 7            |
| sink degreee sum  | 1991   | 1999         |
| sink max degree   | 3      | 8            |
---------------------------------------------

---------------------------------------------
|                (200,5000)                 |
---------------------------------------------
| criteria          | sorted | random order |
| source degree sum | 5198   | 5198         |
| source max degree | 2      | 3            |
| sink degreee sum  | 5198   | 5198         |
| sink max degree   | 43     | 54           |
---------------------------------------------

Answer 2

You can solve this as a fixed-charge transportation problem on a complete bipartite directed graph with sources on one side and sinks on the other. Explicitly, let $S$ be the set of sources and let $T$ be the set of sinks. For $i\in S$ and $j\in T$, define flow variable $x_{i,j} \ge 0$, with upper bound $u_{i,j} = \min(s_i,-s_j)$, where $s_i$ is the supply or demand at node $i\in S \cup T$, and design variable $y_{i,j} \in \{0,1\}$. Then the problem is to minimize $\sum_{i\in S} \sum_{j\in T} y_{i,j}$ subject to: \begin{align} \sum_j x_{i,j} - \sum_j x_{j,i} &= s_i &&\text{for $i\in S \cup T$}\\ 0 \le x_{i,j} &\le u_{i,j} y_{i,j} &&\text{for $i\in S,\ j\in T$}\\ y_{i,j} &\in \{0,1\} &&\text{for $i\in S,\ j\in T$} \end{align}