# pplp / benchmark / costflow.py

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50``` ``` 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'] ```