Min-cost-flow problem

# Solving a min-cost-flow problem using the Xpress Python interface.
#
# (C) 1983-2025 Fair Isaac Corporation

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
flow = p.addVariables(m)

p.addConstraint(xp.Dot(A, flow) == -demand)
p.setObjective(xp.Dot(cost, flow))

p.optimize()

print(cost, demand)

sol = p.getSolution(flow)

for i in range(m):
    print('flow on', E[i], ':', sol[i])