1. Hakan Ardo
  2. pplp

Source

pplp / benchmark / costflow.py


def costflow(graph):
    from pplp import LinearProgram
    lp = LinearProgram()
    flow = []

    for a in graph.arcs:
        arc_flow = lp.Var()
        lp.add_constraint( 0 <= arc_flow <= a.capacity )
        lp.objective += arc_flow * a.cost
        flow.append(arc_flow)

    for n in graph.nodes:
        total_flow = 0
        for a in n.outgoing:
            total_flow += flow[a.index]
        for a in n.incomming:
            total_flow -= flow[a.index]
        lp.add_constraint( total_flow == 0 )

    mincost = lp.minimize()
    return mincost

def costflow_cvxopt(graph):
    from cvxopt import spmatrix, matrix, solvers
    c = matrix([float(a.cost) for a in graph.arcs])
    G = spmatrix([], [], [], (2*len(c), len(c)))
    h = matrix([0.0] * G.size[0])
    A = spmatrix([], [], [], (len(graph.outgoing_first)-1, len(c)))
    b = matrix([0.0] * A.size[0])        
    Gidx = Aidx = 0

    for a in graph.arcs:
        G[Gidx, a.index] = 1.0
        h[Gidx] = float(a.capacity)
        Gidx += 1
        G[Gidx, a.index] = -1.0
        h[Gidx] = 0.0
        Gidx += 1

    for n in graph.nodes:
        for a in n.outgoing:
            A[Aidx, a.index] = -1.0
        for a in n.incomming:
            A[Aidx, a.index] = 1.0
        b[Aidx] = 0.0
        Aidx += 1

    sol = solvers.lp(c, G, h, A, b, 'glpk')
    return sol['primal objective']