Minimun cost flow not satisying all nodes in Networkx

user_12181035 0
Viewed 31

I am trying to solve a minimum cost flow problem given in the paper: https://www.researchgate.net/publication/334843578_Balanced_Clustering_A_Uniform_Model_and_Fast_Algorithm. The paper guarantees a feasible solution provided certain conditions are met. I am using Networkx to solve the problem for a dummy graph; however, Networkx can't find a feasible solution to the problem.

Hereunder is the code that I am using to solve the problem:

# directed graph
G = nx.MultiDiGraph()

# no. of nodes in graph
Nxi = 5 #source nodes
Nci = 2 #intermediate nodes
Ns = 1 #sink node

# define edges
e_x_c = [('x_'+str(i),'c_'+str(j), {'weight': 1, 'capacity': 1}) for i in range(Nxi) for j in range(Nci)] # each x_i is only connected to each c_i
e_c_s = [('c_'+str(j),'s', {'weight': (n+1)**2 - n**2, 'capacity': 1}) for n in range(Nxi) for j in range(Nci) ] # nxi no. of edges with increasing weights for each c_i to s. 
G.add_edges_from(e_x_c)
G.add_edges_from(e_c_s)

# define nodes
nx.set_node_attributes(G, name='demand', values={**{'x_'+str(i):1 for i in range(Nxi)}, **{'c_'+str(j):0 for j in range(Nci)}, **{'s':-Nxi}})

nx.min_cost_flow(G)

Graph looks like:

enter image description here

Any pointers on where I am doing it wrong?

networkx python
1 Answers

If you followed the paper, they define the b>0 as flow produced and b<0 as the consumed flow. You implemented it in this way in your code. Now the networkx function expects you to define a demand, d<0 the node produces flow , whereas d>0 the node consumes flow.

In your case the red nodes each consume 1 flow and the green node produces 5. Since you have no edges from green to red, the flow can not be distributed from producers to consumers.

If you change the sign of the number you input as the demand (e.g. transform b to d), nx.minimum_cost_flow() finds a solution:

# directed graph
G = nx.MultiDiGraph()

# no. of nodes in graph
Nxi = 5 #source nodes
Nci = 2 #intermediate nodes
Ns = 1 #sink node

# define edges
e_x_c = [('x_'+str(i),'c_'+str(j), {'weight': 1, 'capacity': 1}) for i in range(Nxi) for j in range(Nci)] # each x_i is only connected to each c_i
e_c_s = [('c_'+str(j),'s', {'weight': (n+1)**2 - n**2, 'capacity': 2}) for n in range(Nxi) for j in range(Nci) ] # nxi no. of edges with increasing weights for each c_i to s. 
G.add_edges_from(e_x_c)
G.add_edges_from(e_c_s)

# define nodes and change sign so -b = d
nx.set_node_attributes(G, name='demand', values={**{'x_'+str(i):-1 for i in range(Nxi)}, **{'c_'+str(j):0 for j in range(Nci)}, **{'s':Nxi}})

nx.min_cost_flow(G)

Output:

#Output:
{'x_0': {'c_0': {0: 1}, 'c_1': {0: 0}},
 'c_0': {'s': {0: 2, 1: 1, 2: 0, 3: 0, 4: 0}},
 'c_1': {'s': {0: 2, 1: 0, 2: 0, 3: 0, 4: 0}},
 'x_1': {'c_0': {0: 1}, 'c_1': {0: 0}},
 'x_2': {'c_0': {0: 0}, 'c_1': {0: 1}},
 'x_3': {'c_0': {0: 0}, 'c_1': {0: 1}},
 'x_4': {'c_0': {0: 1}, 'c_1': {0: 0}},
 's': {}}
user_162931910
Related