Solving general minimum cost flow problems using only one demand and one supply node

Question

This is a practice in using reduction. Suppose I have a solver that only allows input to a MCF that specifies only one demand and one supply node. How could I use this solver to solve general MCF problems? I have been attempting to solve this with the following toy model:

import gurobipy as gp
from gurobipy import GRB

vertices = [1,2,3,4,5,6]

arcs, capacity = gp.multidict({
    (1,2) : 2,
    (1,6) : 2,
    (2,1) : 2,
    (2,5) : 2,
    (3,2) : 2,
    (4,3) : 2,
    (4,2) : 2,
    (5,4) : 2,
    (5,6) : 2,
    (6,5) : 2
})

cost = {
    (1,2) : 1,
    (1,6) : 1,
    (2,1) : 1,
    (2,5) : 1,
    (3,2) : 1,
    (4,3) : 1,
    (4,2) : 1,
    (5,4) : 1,
    (5,6) : 1,
    (6,5) : 1
}

supply = {
    1 : -1,
    2 : 2,
    3 : -2,
    4 : 3,
    5 : 0,
    6 : -2
}

m = gp.Model("test")

flow = m.addVars(arcs, obj = cost, name = "flow")

m.addConstrs(
    (flow.sum(i,j) <= capacity[i,j] for i,j in arcs), "cap")

m.addConstrs(
    (flow.sum(i,'*') - flow.sum('*',i) == supply[i] for i in vertices), "conservation")

m.optimize()

if m.status == GRB.OPTIMAL:
        solution = m.getAttr('x', flow)
        for i, j in arcs:
            if solution[i, j] > 0:
                print('%s -> %s: %g' % (i, j, solution[i, j]))

Now suppose I wish to solve this type of problem with the solver mentioned above. I could make a few changes to the code and get another feasible model:

import gurobipy as gp
from gurobipy import GRB

vertices = [1,2,3,4,5,6]

# we need to change the capacities here to get a feasible model
arcs, capacity = gp.multidict({
    (1,2) : 3,
    (1,6) : 2,
    (2,1) : 2,
    (2,5) : 3,
    (3,2) : 2,
    (4,3) : 2,
    (4,2) : 2,
    (5,4) : 2,
    (5,6) : 5,
    (6,5) : 2
})

cost = {
    (1,2) : 1,
    (1,6) : 1,
    (2,1) : 1,
    (2,5) : 1,
    (3,2) : 1,
    (4,3) : 1,
    (4,2) : 1,
    (5,4) : 1,
    (5,6) : 1,
    (6,5) : 1
}

# Now b1 carries all supply and b6 carries all demand
supply = {
    1 : 5,
    2 : 0,
    3 : 0,
    4 : 0,
    5 : 0,
    6 : -5
}

m = gp.Model("test")

flow = m.addVars(arcs, obj = cost, name = "flow")

m.addConstrs(
    (flow.sum(i,j) <= capacity[i,j] for i,j in arcs), "cap")

m.addConstrs(
    (flow.sum(i,'*') - flow.sum('*',i) == supply[i] for i in vertices), "conservation")

m.optimize()

if m.status == GRB.OPTIMAL:
        solution = m.getAttr('x', flow)
        for i, j in arcs:
            if solution[i, j] > 0:
                print('%s -> %s: %g' % (i, j, solution[i, j]))

It does not seem obvious at all to me how to convert this new solution to the original problem. It seems analogous to trying to "unmix" paint here, and I don't think a Fourier transform is applicable in this scenario. In order to get the feasible model, I also had to make changes to the capacities to ensure feasibility, so one idea may be to try to somehow "unwind" these changes in capacity to trace back the steps this flow would take in the general context, but I have no idea how to formalize this. It seems intuitively that better solutions in the one supply/demand node problem would correspond to better solutions in the general case since the costs are equivalent, but again, I am not sure how to formalize this.

Answer 1

Introduce a supersource node $s$, a supersink node $t$, arcs from $s$ to each source, and arcs from each sink to $t$. Arc $(s,i)$ has zero cost and capacity equal to supply[i]. Arc $(i,t)$ has zero cost and capacity equal to -supply[i]. All original nodes have supply zero, $s$ has supply equal to the sum of positive supplies, and $t$ has supply equal to the sum of negative supplies (equivalently, demand equal to the sum of demands).