| |||||||||||
Min-cost-flow problem Description solving a min-cost-flow problem using the Xpress Python interface. Further explanation of this example: 'Xpress Python Reference Manual'
Source Files By clicking on a file name, a preview is opened at the bottom of this page.
netflow.py # Example: solving a min-cost-flow problem # using the Xpress Python interface # # (C) Fair Isaac Corp., 1983-2024 import numpy as np # for matrix and vector products import xpress as xp # digraph definition V = [1, 2, 3, 4, 5] # vertices E = [[1, 2], [1, 4], [2, 3], [3, 4], [4, 5], [5, 1]] # arcs n = len(V) # number of nodes m = len(E) # number of arcs # Generate incidence matrix: begin with a NxM zero matrix A = np.zeros((n,m)) # Then for each column i of the matrix, add a -1 in correspondence to # the tail of the arc and a 1 for the head of the arc. Because Python # uses 0-indexing, the row of A should be the node index minus one. for i, edge in enumerate(E): A[edge[0] - 1][i] = -1 A[edge[1] - 1][i] = 1 print("incidence matrix:\n", A) # One (random) demand for each node demand = np.random.randint(100, size=n) # Balance demand at nodes demand[0] = - sum(demand[1:]) cost = np.random.randint(20, size=m) # Integer, random arc costs p = xp.problem('network flow') # Flow variables declared on arcs---use dtype parameter to ensure # NumPy handles these as vectors of Xpress objects. flow = np.array([p.addVariable() for i in E], dtype=xp.npvar) p.addConstraint(xp.Dot(A, flow) == - demand) p.setObjective(xp.Dot(cost, flow)) p.optimize() print(cost, demand) for i in range(m): print('flow on', E[i], ':', p.getSolution(flow[i])) | |||||||||||
© Copyright 2024 Fair Isaac Corporation. |