1
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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).

$\endgroup$
4
  • $\begingroup$ by "arcs from $s$ to each source, and arcs from each sink to $t$", do you mean constructing arcs between the new supersource and the sources from the original problem (i.e. say $s=b_1$, then we connect $b_1$ with all nodes that have $b_i >0$)? $\endgroup$
    – user620842
    Feb 22 at 21:52
  • 1
    $\begingroup$ @user620842 Yes, and a similar idea for the sinks from the original problem to the new supersink. $\endgroup$
    – RobPratt
    Feb 22 at 21:55
  • $\begingroup$ okay! And in this new graph, are these new arcs added onto the previous graph, or is this a new graph independent of the original (i.e. only contains the arcs $(s,i)$ and $(i,t)$ as you described)? $\endgroup$
    – user620842
    Feb 22 at 22:03
  • 1
    $\begingroup$ The two new nodes and associated arcs are appended to the original graph. The only changes to the original nodes are that the supplies become 0. $\endgroup$
    – RobPratt
    Feb 22 at 22:25

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.